2485. Find the Pivot Integer
Description
Given a positive integer n
, find the pivot integer x
such that:
- The sum of all elements between
1
andx
inclusively equals the sum of all elements betweenx
andn
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 <= 1000
Solutions
Solution 1: Enumeration
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)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
Solution 2: Mathematics
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)$.
1 2 3 4 5 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 |