A staircase has n steps, numbered 1 through n starting from the bottom. Each step's structural load rating is simply its step number. A step x, where 1 <= x <= n, is called the balance step if the sum of the load ratings of steps 1 through x (inclusive) equals the sum of the load ratings of steps x through n (inclusive) -- step x itself is counted in both sums. Determine the balance step. It is guaranteed that at most one balance step exists for any given n.
A single line containing the integer n.
Print the balance step number x if one exists; otherwise print -1.
1 <= n <= 200000
Example 1
Input
49
Expected
35
Explanation
The sum of steps 1 through 35 is 35*36/2 = 630. The sum of steps 35 through 49 is (sum of 1 through 49) minus (sum of 1 through 34) = 1225 - 595 = 630. Both sums equal 630, so step 35 is the balance step.
Example 2
Input
5
Expected
-1
Explanation
For n=5, no step x makes the sum of 1..x equal the sum of x..5: checking x=1..5 gives left/right sums of (1,15),(3,14),(6,12),(10,9),(15,5), none equal. So the output is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →