Find the Pivot Integer — Easy Problem & Solution

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.

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

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

Compute total = n(n+1)/2.
Sweep x from 1 to n, maintaining prefix = 1 + … + x.
Return x the moment prefix == total - prefix + x.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue