Find the Pivot Integer

Easy
689.

Find the Pivot Integer

Find the Pivot Integer is an easy coding problem on math and prefix sum, asked in TCS, Infosys and Capgemini interviews.

Find the integer x such that the sum of 1 through x equals the sum of x through n. Note that x itself is counted on both sides.

Return that x, or -1 if it does not exist. It is unique when it exists.

Example 1

Input
n = 8
Output
6
Explanation
1 + … + 6 = 21 and 6 + 7 + 8 = 21.

Example 2

Input
n = 1
Output
1
Explanation
Both sides are just the number 1.

Example 3

Input
n = 4
Output
-1

Constraints

  • 1 <= n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var pivotInteger = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Pivot Integer — Solution in Python, Java & C++

Find the Pivot Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Pivot Integer is an easy coding problem on math and prefix sum, asked in TCS, Infosys and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Math, Prefix Sum
  • Asked at: TCS, Infosys, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Find the integer x such that the sum of 1 through x equals the sum of x through n. Note that x itself is counted on both sides.

Return that x, or -1 if it does not exist. It is unique when it exists.

Example 1

Input: n = 8
Output: 6
Explanation: 1 + … + 6 = 21 and 6 + 7 + 8 = 21.

Example 2

Input: n = 1
Output: 1
Explanation: Both sides are just the number 1.

Example 3

Input: n = 4
Output: -1

Constraints

  • 1 <= n <= 1000

Hints for Find the Pivot Integer

  1. Hint 1

    The total 1 + … + n is n(n+1)/2, which is cheap to compute.

  2. Hint 2

    If the prefix up to x is p, the suffix from x is total - p + x.

  3. Hint 3

    Setting them equal gives 2p - x = total; sweep x and test, or solve x² = total directly.

How to solve Find the Pivot Integer

Both sides are described by the same running prefix, so one sweep with a closed-form total settles it. Algebraically the condition reduces to x² = n(n+1)/2, so the answer exists exactly when that total is a perfect square.

Approach

  1. Compute total = n(n+1)/2.
  2. Sweep x from 1 to n, maintaining prefix = 1 + … + x.
  3. Return x the moment prefix == total - prefix + x.
  4. Return -1 if the sweep finishes.

Why it works

Writing the prefix as x(x+1)/2 and the suffix as total - x(x-1)/2, the equality collapses to x² = total. So the pivot is the integer square root of the total when one exists — which is also why it is unique.

Complexity

  • Time — O(n), or O(1) with the square-root form
  • Space — O(1)

Pitfalls

  • Forgetting that x belongs to both sides shifts the equation by one term and finds nothing.
  • n(n+1)/2 is exact in integers because one of n and n+1 is even — no floating point needed.

Reference solution

Python

def pivotInteger(n: int) -> int:
    total = n * (n + 1) // 2
    prefix = 0
    for x in range(1, n + 1):
        prefix += x
        if prefix == total - prefix + x:
            return x
    return -1

Java

public static int pivotInteger(int n) {
    int total = n * (n + 1) / 2;
    int prefix = 0;
    for (int x = 1; x <= n; x++) {
        prefix += x;
        if (prefix == total - prefix + x) return x;
    }
    return -1;
}

C++

int pivotInteger(int n) {
    int total = n * (n + 1) / 2;
    int prefix = 0;
    for (int x = 1; x <= n; x++) {
        prefix += x;
        if (prefix == total - prefix + x) return x;
    }
    return -1;
}

JavaScript

var pivotInteger = function(n) {
    var total = (n * (n + 1)) / 2;
    var prefix = 0;
    for (var x = 1; x <= n; x++) {
        prefix += x;
        if (prefix === total - prefix + x) return x;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Prefix Sum