Find the Pivot Integer
EasyPrompt
Given a positive integer n, find the pivot integer x such that:
- The sum of all elements between
1andxinclusively equals the sum of all elements betweenxandninclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.
Example 1:
Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.Example 2:
Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.Example 3:
Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.
Constraints:
1 <= n <= 1000
Approaches
4 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. We can simply test every possible value for the pivot integer x from 1 to n. For each candidate x, we calculate the sum of all numbers from 1 to x and the sum of all numbers from x to n. If these two sums are equal, we have found our pivot.
Algorithm
- Iterate through each integer
xfrom1tonas a potential pivot. - For each
x, initialize two variables,leftSumandrightSum, to zero. - Calculate
leftSumby iterating from1toxand adding each number. - Calculate
rightSumby iterating fromxtonand adding each number. - If
leftSumis equal torightSum, thenxis the pivot integer. Returnx. - If the loop completes without finding a pivot, it means no such integer exists. Return
-1.
Walkthrough
The brute-force method involves a nested loop structure. The outer loop iterates through all possible pivot candidates x from 1 to n. Inside this loop, two separate inner loops are used. The first inner loop calculates the sum of the elements on the left side of x (i.e., from 1 to x inclusive). The second inner loop calculates the sum of the elements on the right side (i.e., from x to n inclusive). After calculating both sums, we compare them. If they are identical, we've found the pivot and can return x immediately. If the outer loop finishes without finding any such x, we conclude that no pivot exists and return -1.
class Solution { public int pivotInteger(int n) { for (int x = 1; x <= n; x++) { int leftSum = 0; for (int i = 1; i <= x; i++) { leftSum += i; } int rightSum = 0; for (int j = x; j <= n; j++) { rightSum += j; } if (leftSum == rightSum) { return x; } } return -1; }}Complexity
Time
O(n^2) - The outer loop runs `n` times. For each iteration, the inner loops for calculating `leftSum` and `rightSum` can run up to `n` times, resulting in a time complexity proportional to n*n.
Space
O(1) - We only use a few variables to store the sums and loop counters, so the space required is constant.
Trade-offs
Pros
Very simple to understand and implement.
Correctly solves the problem for the given constraints.
Cons
Highly inefficient due to nested loops, leading to a quadratic time complexity.
Will be very slow for large values of
nand may lead to a 'Time Limit Exceeded' error in competitive programming platforms.
Solutions
Solution
class Solution {public int pivotInteger(int n) { for (int x = 1; x <= n; ++x) { if ((1 + x) * x == (x + n) * (n - x + 1)) { return x; } } return -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.