Vultr DocsLatest Content

Find the Pivot Integer

Updated on 28 May, 2025
Find the Pivot Integer header image

Problem Statement

Given a positive integer n, the challenge is to find a pivot integer x that divides the sequence of numbers from 1 to n into two parts, where the sum of all integers from 1 to x (inclusive) equals the sum of integers from x to n (inclusive). The function should return this pivot integer x. If such an integer does not exist, the function should return -1. It is specified that there can be at most one valid pivot index for any input n.

Examples

Example 1

Input:

n = 8

Output:

6

Explanation:

6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

Example 2

Input:

n = 1

Output:

1

Explanation:

1 is the pivot integer since: 1 = 1.

Example 3

Input:

n = 4

Output:

-1

Explanation:

It can be proved that no such integer exist.

Constraints

  • 1 <= n <= 1000

Approach and Intuition

Let's delve into the methodology to find the pivot integer that evenly splits the sum of numbers from 1 to n:

  1. Sum Calculation: First calculate the total sum, S, of all numbers from 1 to n. This can be efficiently done using the formula for the sum of the first n natural numbers: S = n * (n + 1) / 2.

  2. Feasibility Check: If S is odd, directly return -1 since an odd number cannot be evenly split into two equal integer sums. This check increases the efficiency for half of the cases where n leads to an odd sum.

  3. Iterative Search for Pivot: If S is even, initialize a running sum, sum_x, iterating from 1 to n. For each integer i, add i to sum_x and check if 2 * sum_x is equal to S. If so, i is the desired pivot integer.

  4. Return Result: If you find such an i, return it. If the loop completes without finding an i, return -1, indicating no pivot index exists for the given n.

This approach is efficient, straightforward, and leverages simple mathematical properties to reduce unnecessary computations.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
 public:
  int findPivot(int totalNums) {
        const int cumulativeSum = (totalNums * (totalNums + 1) / 2);
        const int pivotPoint = sqrt(cumulativeSum);
        // Return pivotPoint if its square equals cumulativeSum; otherwise, return -1
        return pivotPoint * pivotPoint == cumulativeSum ? pivotPoint : -1;
  }
};

The given C++ code defines a method findPivot within a class Solution. This method computes the pivot integer for a sequence from 1 to totalNums. Follow these steps to understand how the code operates:

  1. Calculate cumulativeSum which is the sum of all numbers from 1 to totalNums using the formula totalNums * (totalNums + 1) / 2.

  2. Determine pivotPoint by computing the integer square root of cumulativeSum.

  3. Check if the square of the pivotPoint equals cumulativeSum. If true, pivotPoint is returned as it is a perfect root; otherwise, the method returns -1 indicating no perfect square root exists for cumulativeSum.

This approach effectively identifies the pivot integer by checking if the total cumulative sum of numbers up to totalNums is a perfect square, demonstrating a mathematical and algorithmic solution to find the square root or determine the non-existence based on the given range.

java 
class Solution {
  public int findPivot(int num) {
        final int total = (num * (num + 1) / 2);
        final int pivotValue = (int) Math.sqrt(total);
        return pivotValue * pivotValue == total ? pivotValue : -1;
  }
}

The Java solution provided addresses the problem of finding a pivot integer. This pivot integer is such that the sum of all integers up to a given number num matches the square of the pivot integer. If no such integer exists, the function returns -1.

Process:

  1. Calculate the sum of integers from 1 to num using the formula: total = num * (num + 1) / 2
  2. Determine if this total is a perfect square by taking its square root, truncating the decimal, and squaring it again to check if it matches the original total.
  3. If it matches, the pivot value (square root of the total) is returned; otherwise, -1 is returned to indicate no such pivot exists.

This method efficiently checks for the pivot by utilizing mathematical properties and ensures an optimal performance without iterating unnecessarily through possible numbers.

python 
class Finder:
  def findPerfectSquare(self, x: int) -> int:
        computed_sum = (x * (x + 1) // 2)
        potential_pivot = int(math.sqrt(computed_sum))
        return potential_pivot if potential_pivot * potential_pivot == computed_sum else -1

The Python3 program provides a method to find the pivot integer for a given number x. The method named findPerfectSquare in the Finder class calculates the sum of first x natural numbers using the formula x * (x + 1) // 2. This sum is then checked to see if it is a perfect square.

Here is a concise breakdown of how the solution works:

  • Calculate the sum of the first x natural numbers.
  • Compute the square root of this sum and check if the square root, when squared, equals the original sum.
  • If the squared value matches the sum, return the potential pivot which is the integer square root.
  • Otherwise, return -1 to indicate that no pivot integer exists that makes the sum a perfect square.

The method efficiently determines if the computed sum of numbers can be represented as a perfect square, offering a straightforward way to find the pivot integer if it exists.

Comments

No comments yet.