Skip to content

2485. Find the Pivot Integer 👍

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  int pivotInteger(int n) {
    // 1 + 2 + ... + x = x + ... + n
    // (1 + x) * x / 2 = (x + n) * (n - x + 1) / 2
    //         x + x^2 = nx - x^2 + x + n^2 - nx + n
    //         2 * x^2 = n^2 + n
    //               x = sqrt((n^2 + n) / 2)
    const int y = (n * n + n) / 2;
    const int x = sqrt(y);
    return x * x == y ? x : -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public int pivotInteger(int n) {
    // 1 + 2 + ... + x = x + ... + n
    // (1 + x) * x / 2 = (x + n) * (n - x + 1) / 2
    //         x + x^2 = nx - x^2 + x + n^2 - nx + n
    //         2 * x^2 = n^2 + n
    //               x = sqrt((n^2 + n) / 2)
    final int y = (n * n + n) / 2;
    final int x = (int) Math.sqrt(y);
    return x * x == y ? x : -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def pivotInteger(self, n: int) -> int:
    # 1 + 2 + ... + x = x + ... + n
    # (1 + x) * x // 2 = (x + n) * (n - x + 1) // 2
    #         x + x^2 = nx - x^2 + x + n^2 - nx + n
    #         2 * x^2 = n^2 + n
    #               x = sqrt((n^2 + n) // 2)
    y = (n * n + n) // 2
    x = math.isqrt(y)
    return x if x * x == y else -1