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.
This approach improves upon the brute-force method by optimizing the sum calculations. Instead of recalculating the sums from scratch in each iteration, we can use a running sum for the left side and derive the right side's sum from the total sum. This reduces the complexity from quadratic to linear.
Algorithm
- First, calculate the total sum of numbers from
1tonusing the formulatotalSum = n * (n + 1) / 2. - Initialize a variable
leftSum = 0. - Iterate with a variable
xfrom1ton. - In each iteration, update
leftSumby adding the currentx:leftSum += x. - The
rightSumcan be derived fromtotalSumandleftSum. The sum fromxtonistotalSum - (sum from 1 to x-1). This is equivalent tototalSum - leftSum + x. - Check if
leftSum == rightSum. If they are equal,xis the pivot. Returnx. - If the loop finishes, no pivot was found. Return
-1.
Walkthrough
We can avoid the nested loops by being smarter about how we calculate the sums. First, we compute the total sum of numbers from 1 to n once. Then, we iterate through the potential pivots x from 1 to n. We maintain a leftSum which is the sum of numbers from 1 up to the current x. In each step of the loop, we add x to leftSum. The rightSum (sum from x to n) can then be calculated efficiently as totalSum - leftSum + x. We add x back because leftSum includes x, and we want the sum from x to n, not x+1 to n. We then compare leftSum and rightSum. This process requires only a single pass through the numbers.
class Solution { public int pivotInteger(int n) { int totalSum = n * (n + 1) / 2; int leftSum = 0; for (int x = 1; x <= n; x++) { leftSum += x; int rightSum = totalSum - leftSum + x; if (leftSum == rightSum) { return x; } } return -1; }}Complexity
Time
O(n) - We iterate through the numbers from 1 to `n` only once, and all operations inside the loop are constant time.
Space
O(1) - Constant extra space is used for variables like `totalSum` and `leftSum`.
Trade-offs
Pros
Significantly more efficient than the O(n^2) brute-force approach.
Still easy to understand and implement.
Cons
While much better than the O(n^2) approach, it is still not the most optimal solution.
For extremely large values of
n(beyond the problem constraints), a linear scan might still be too slow.
A more efficient approach is to use binary search. We can observe that as the candidate pivot x increases, the left sum (1 + ... + x) increases and the right sum (x + ... + n) decreases. This monotonic property of the difference between the two sums allows us to efficiently search for the pivot.
Algorithm
- Define a search range for the pivot
xfromleft = 1toright = n. - While
left <= right:- Calculate the middle element
mid = left + (right - left) / 2. - Calculate the sum from
1tomid(left sum) using the formulamid * (mid + 1) / 2. - Calculate the sum from
midton(right sum). This can be found by(total sum) - (sum from 1 to mid-1), which is(n*(n+1)/2) - (mid*(mid-1)/2). - If
leftSum == rightSum,midis the pivot. Returnmid. - If
leftSum < rightSum, the pivot must be larger thanmid. Adjust the search space to the right half:left = mid + 1. - If
leftSum > rightSum, the pivot must be smaller thanmid. Adjust the search space to the left half:right = mid - 1.
- Calculate the middle element
- If the loop terminates, no pivot was found. Return
-1.
Walkthrough
We can apply binary search on the possible values of x, which range from 1 to n. For any chosen mid value in our search range, we can calculate the left sum and right sum in constant time using the arithmetic series sum formula: sum(1..k) = k*(k+1)/2. We compare the two sums. If the left sum is smaller than the right sum, it implies our chosen mid is too small, and the actual pivot must be in the right half of the search range. Conversely, if the left sum is larger, the pivot must be in the left half. If the sums are equal, we have found our pivot. This process repeatedly halves the search space, leading to a logarithmic time complexity.
class Solution { public int pivotInteger(int n) { int left = 1, right = n; while (left <= right) { int mid = left + (right - left) / 2; int leftSum = mid * (mid + 1) / 2; // Sum from x to n is TotalSum - Sum(1 to x-1) int rightSum = (n * (n + 1) / 2) - (mid * (mid - 1) / 2); if (leftSum == rightSum) { return mid; } else if (leftSum < rightSum) { left = mid + 1; } else { right = mid - 1; } } return -1; }}Complexity
Time
O(log n) - Binary search halves the search space of size `n` in each iteration.
Space
O(1) - Only a few variables are needed to keep track of the search boundaries, requiring constant space.
Trade-offs
Pros
Very efficient with O(log n) time complexity.
Optimal for problems with very large constraints on
n.
Cons
Slightly more complex to conceptualize and implement compared to a linear scan.
The performance gain is only significant for very large
n.
The most optimal solution involves reducing the problem to a simple mathematical equation. By expressing the sums on both sides of the pivot condition algebraically, we can solve for x directly in terms of n.
Algorithm
- Start with the pivot condition:
sum(1..x) = sum(x..n). - Express the sums using the arithmetic series formula:
x*(x+1)/2 = n*(n+1)/2 - (x-1)*x/2. - Simplify the equation algebraically:
x^2 + x = n^2 + n - (x^2 - x)2*x^2 = n^2 + nx^2 = (n^2 + n) / 2
- This means
xmust be the square root of the total sum of numbers from1ton. - Calculate
totalSum = (n*n + n) / 2. - Find the integer square root of
totalSum. Let's call itpivot. - Verify if
totalSumis a perfect square by checking ifpivot * pivot == totalSum. - If it is,
pivotis the answer. Returnpivot. - Otherwise, no integer pivot exists. Return
-1.
Walkthrough
The condition that the sum of elements from 1 to x equals the sum from x to n can be translated into a mathematical formula.
Let S_n be the sum of integers from 1 to n. The condition is S_x = S_n - S_{x-1}.
Substituting the formula for the sum of an arithmetic series, k(k+1)/2, we get:
x(x+1)/2 = n(n+1)/2 - (x-1)x/2.
Solving this equation for x reveals a remarkable simplification: x^2 = n(n+1)/2.
This means that the pivot integer x is simply the square root of the total sum of numbers from 1 to n. Therefore, the problem reduces to calculating this total sum, finding its square root, and checking if the result is a whole number. If it is, that number is our pivot; otherwise, no integer pivot exists.
class Solution { public int pivotInteger(int n) { // The condition sum(1..x) == sum(x..n) simplifies to // x*x = (n * (n + 1)) / 2 int totalSum = (n * n + n) / 2; int pivot = (int) Math.sqrt(totalSum); // Check if totalSum is a perfect square if (pivot * pivot == totalSum) { return pivot; } return -1; }}Complexity
Time
O(1) - The solution involves a handful of arithmetic operations and a square root function, all of which take constant time.
Space
O(1) - The calculation requires a fixed number of variables, regardless of the input `n`.
Trade-offs
Pros
Extremely efficient, providing a solution in constant time.
Elegant and concise.
Cons
Requires mathematical derivation which might not be immediately obvious.
Potential for floating-point precision issues if not handled carefully (though using integer arithmetic for the check avoids this).
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; }}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; }};class Solution: def pivotInteger(self, n: int) -> int: for x in range(1, n + 1): if (1 + x) * x == (x + n) * (n - x + 1): return x return - 1Video 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.