LeetCode 2485. Find the Pivot Integer Solution in Java, C++, Python & More | Explanation + Code

Description

Given a positive integer n, find the pivot integer x such that:

• The sum of all elements between 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 <= 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) × x = (x + n) × (n - x + 1)

The time complexity is O(n), where n is the given positive integer n. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustPHP

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 -1(code-box)

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; } }(code-box)

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; } };(code-box)

func pivotInteger(n int) int { for x := 1; x <= n; x++ { if (1+x)*x == (x+n)*(n-x+1) { return x } } return -1 }(code-box)

function pivotInteger(n: number): number { for (let x = 1; x <= n; ++x) { if ((1 + x) * x === (x + n) * (n - x + 1)) { return x; } } return -1; }(code-box)

impl Solution { pub fn pivot_integer(n: i32) -> i32 { let y = (n * (n + 1)) / 2; let x = (y as f64).sqrt() as i32; if x * x == y { return x; } -1 } }(code-box)

class Solution { /** * @param Integer $n * @return Integer */ function pivotInteger($n) { $sum = ($n * ($n + 1)) / 2; $pre = 0; for ($i = 1; $i <= $n; $i++) { if ($pre + $i === $sum - $pre) { return $i; } $pre += $i; } return -1; } }(code-box)

Solution 2: Mathematics

We can transform the above equation to get:

n × (n + 1) = 2 × x²

That is:

x = √^{n × (n + 1)}⁄₂

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).

PythonJavaC++GoTypeScript

class Solution: def pivotInteger(self, n: int) -> int: y = n * (n + 1) // 2 x = int(sqrt(y)) return x if x * x == y else -1(code-box)

class Solution { public int pivotInteger(int n) { int y = n * (n + 1) / 2; int x = (int) Math.sqrt(y); return x * x == y ? x : -1; } }(code-box)

class Solution { public: int pivotInteger(int n) { int y = n * (n + 1) / 2; int x = sqrt(y); return x * x == y ? x : -1; } };(code-box)

func pivotInteger(n int) int { y := n * (n + 1) / 2 x := int(math.Sqrt(float64(y))) if x*x == y { return x } return -1 }(code-box)

function pivotInteger(n: number): number { const y = Math.floor((n * (n + 1)) / 2); const x = Math.floor(Math.sqrt(y)); return x * x === y ? x : -1; }(code-box)