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.
The sum of the first
n
natural numbers is given by the formulan * (n + 1) / 2
. Let’s denote this assum
.If
x
is the pivot, the sum of numbers from 1 tox
isx * (x + 1) / 2
, and the sum of numbers fromx
ton
would be the totalsum
minus the sum of numbers from 1 tox
and plusx
(sincex
is included in both parts).
So, the equation becomes x * (x + 1) / 2 == sum - x * (x + 1) / 2 + x
.
Solving this equation, we can move terms around to get
2 * x * (x + 1) / 2 - x == sum
, orx * (x + 1) - x == sum
.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.
|
|
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.