Find the Pivot Integer

easy math prefix sum

Problem

Given a positive integer n, find the pivot integer x such that the sum of all integers from 1 to x (inclusive) equals the sum of all integers from x to n (inclusive). Return that pivot x, or -1 if none exists. There is at most one valid pivot.

Inputn = 8

Output6

1 + 2 + 3 + 4 + 5 + 6 = 21 and 6 + 7 + 8 = 21, so 6 is the pivot.

n (1 to 1000)

def pivotInteger(n):
    total = n * (n + 1) // 2     # sum of 1..n
    left = 0                     # running prefix sum 1..x
    for x in range(1, n + 1):
        left += x                # extend prefix to include x
        # right side is sum of x..n = total - (left - x)
        right = total - left + x
        if left == right:        # both halves balance at x
            return x
    return -1                    # no pivot exists

function pivotInteger(n) {
  const total = (n * (n + 1)) / 2;   // sum of 1..n
  let left = 0;                       // running prefix sum 1..x
  for (let x = 1; x <= n; x++) {
    left += x;                        // extend prefix to include x
    // right side is sum of x..n = total - (left - x)
    const right = total - left + x;
    if (left === right) {             // both halves balance at x
      return x;
    }
  }
  return -1;                          // no pivot exists
}

int pivotInteger(int n) {
    int total = n * (n + 1) / 2;   // sum of 1..n
    int left = 0;                  // running prefix sum 1..x
    for (int x = 1; x <= n; x++) {
        left += x;                 // extend prefix to include x
        // right side is sum of x..n = total - (left - x)
        int right = total - left + x;
        if (left == right) {       // both halves balance at x
            return x;
        }
    }
    return -1;                     // no pivot exists
}

int pivotInteger(int n) {
    int total = n * (n + 1) / 2;   // sum of 1..n
    int left = 0;                  // running prefix sum 1..x
    for (int x = 1; x <= n; x++) {
        left += x;                 // extend prefix to include x
        // right side is sum of x..n = total - (left - x)
        int right = total - left + x;
        if (left == right) {       // both halves balance at x
            return x;
        }
    }
    return -1;                     // no pivot exists
}

Explanation

We want a split point x where the left block 1 + 2 + … + x weighs exactly the same as the right block x + (x+1) + … + n. Note that x itself belongs to both sums, which is what makes a balance possible.

The whole range sums to total = n·(n+1)/2. As we sweep x from 1 upward we keep a running prefix sum left = 1 + 2 + … + x, adding one new term per step. The elements strictly before x sum to left - x, so the right block is everything not yet consumed plus x again: right = total - (left - x).

At each x we simply compare left against right. The moment they are equal we have found the pivot and return it. The left sum only grows while the right sum only shrinks, so they cross at most once — matching the guarantee that there is at most one pivot.

If the loop finishes without a match, no balance point exists and we return -1. For n = 8 the prefix reaches 21 at x = 6, where the right block 6 + 7 + 8 also equals 21, so the answer is 6.

A purely arithmetic shortcut also works: the balance condition simplifies to x² = total, so x is the integer square root of total when that is a perfect square. The prefix-sum sweep shown here is the same idea made explicit step by step.

Time: O(n) Space: O(1)