Find the Pivot Integer

We want to find a number x in the range [1, n] that divides the range into two parts where the sum of all numbers in both parts is equal.

  1. The sum of the first n natural numbers is given by the formula n * (n + 1) / 2. Let’s denote this as sum.

  2. If x is the pivot, the sum of numbers from 1 to x is x * (x + 1) / 2, and the sum of numbers from x to n would be the total sum minus the sum of numbers from 1 to x and plus x (since x is included in both parts).

So, the equation becomes x * (x + 1) / 2 == sum - x * (x + 1) / 2 + x.

  1. Solving this equation, we can move terms around to get 2 * x * (x + 1) / 2 - x == sum, or x * (x + 1) - x == sum.

  2. This simplifies further to x * x == sum.

This means if we can find an x such that x * x equals the sum, then x is the pivot we’re looking for. Since finding the square root is the inverse operation of squaring, we can simply take the square root of sum to find x.

This solution won’t work for all cases, because not all sums of the first n numbers will be perfect squares. This is why the code checks if x * x == sum before returning x. If x * x is not equal to sum, it means no valid pivot x exists, and the function returns -1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import math

class Solution:
    def pivotInteger(self, n: int) -> int:
        total_sum = n * (n + 1) // 2
        x = int(math.sqrt(total_sum))

        if x * x == total_sum:
            return x
        else:
            return -1

Q&A

Why x * x == sum? For n, the sum of [1..n] is sum = n * (n + 1) / 2.

The sum of [1..x] is x * (x + 1) / 2. The sum of [x..n] is n * (n + 1) / 2 - x * (x + 1) / 2 + x. So:

x * (x + 1) / 2 == n * (n + 1) / 2 - x * (x + 1) / 2 + x, x * (x + 1) / 2 + x * (x + 1) / 2 - x == n * (n + 1) / 2, x * (x + 1) - x == sum, x * x == sum.

Thus, we can just use SQRT to find x.