Given a positive integer n, find the pivot integer x such that:
1 and x inclusively equals the sum of all elements between x and n inclusively.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 <= 1000Problem Overview: You are given an integer n. The task is to find an integer x such that the sum of numbers from 1 to x equals the sum of numbers from x to n. If such a number exists, return it. Otherwise return -1.
Approach 1: Brute Force Search (O(n^2) time, O(1) space)
The direct method tries every candidate pivot from 1 to n. For each candidate x, compute the left sum by iterating from 1 to x and the right sum by iterating from x to n. If both sums match, that x is the pivot integer. This approach mirrors the definition of the problem and is useful when first reasoning about the condition. However, each candidate requires two loops, which results in O(n^2) time in the worst case while using constant memory.
The logic here relates closely to the idea of cumulative sums often discussed in Prefix Sum problems. Instead of storing prefix values, the brute force version recomputes them repeatedly.
Approach 2: Optimized Arithmetic Approach (O(1) time, O(1) space)
The key observation is that the sum of the first k integers follows the formula k(k+1)/2. Let S = n(n+1)/2 be the total sum from 1 to n. If x is the pivot, then the sum from 1 to x equals the sum from x to n. Writing this mathematically:
1 + 2 + ... + x = x + (x+1) + ... + n
After simplifying with arithmetic series formulas, the equation becomes x^2 = S. That means the pivot exists only when the total sum is a perfect square. Compute S, take its square root, and check whether it is an integer. If it is, that integer is the pivot. Otherwise no pivot exists.
This turns what initially looks like a cumulative sum search into a simple math check using properties of arithmetic series. The computation runs in constant time and uses constant memory, making it the most efficient solution. The reasoning connects to patterns commonly seen in Math problems where recognizing a formula removes the need for iteration.
Recommended for interviews: Start by explaining the brute force idea since it directly follows the definition of the pivot condition. Then derive the arithmetic relationship and show how the equality simplifies to x^2 = n(n+1)/2. Interviewers expect the optimized mathematical insight because it demonstrates pattern recognition and the ability to convert a Prefix Sum style condition into a constant‑time formula.
This approach involves iterating through each number from 1 to n and checking if it satisfies the given condition of a pivot integer. For each candidate pivot integer x, calculate the sum of numbers from 1 to x using the formula for the sum of an arithmetic series. Similarly, calculate the sum from x to n. Compare these sums to determine if x is a pivot integer.
The function find_pivot iterates through numbers from 1 to n. For each number, it calculates the sum of numbers from 1 to x (sum1) and from x to n (sum2). It returns x if the two sums are equal, otherwise returns -1 at the end.
Time Complexity: O(n).
Space Complexity: O(1).
Instead of iterating through each possible x, we can use mathematical formulation. As the sum from 1 to n is fixed, let's denote the total sum as S. Then, for pivot x, the condition becomes:
(x * (x + 1)) / 2 = (S - ((x - 1) * x) / 2)
From this, derive a formula to find x directly if it exists. Solving algebraically can help us identify the pivot integer without iteration.
This optimized solution uses algebra to directly verify if a number x is a pivot without recalculating sums within the loop.
Time Complexity: O(n).
Space Complexity: O(1).
We can directly enumerate x in the range of [1,..n], and check whether the following equation holds. If it holds, then x is the pivot integer, and we can directly return x.
$
(1 + x) times x = (x + n) times (n - x + 1)
The time complexity is O(n), where n is the given positive integer n. The space complexity is O(1)$.
We can transform the above equation to get:
$
n times (n + 1) = 2 times x^2
That is:
x = \sqrt{\frac{n times (n + 1)}{2}}
If x is an integer, then x is the pivot integer, otherwise there is no pivot integer.
The time complexity is O(1), and the space complexity is O(1)$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Search | Time Complexity: O(n). |
| Optimized Arithmetic Approach | Time Complexity: O(n). |
| Enumeration | — |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | O(n^2) | O(1) | When first reasoning about the problem or validating the pivot definition step by step |
| Optimized Arithmetic Approach | O(1) | O(1) | Preferred solution for interviews and production due to constant time computation |
Find the Pivot Integer | 5 Approaches | Easy Explanation | Leetcode 2485 | codestorywithMIK • codestorywithMIK • 3,879 views views
Watch 9 more video solutions →Practice Find the Pivot Integer with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor