2485. Find the Pivot Integer

  • Hardness: \(\color{green}\textsf{Easy}\)
  • Ralated Topics: Math、Prefix Sum
  • \(\color{blue}\textsf{Weekly Contest 321}\)

一、題目

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

Constraints:

  • 1 <= n <= 1000

二、分析

  • 此題要找 sum([1:x]) == sum([x:n])
  • 當 x=1 開始，即 left = sum([1:1]) 與 right = sum([1:n])。
    • 當指標向右移動，left += (x+1)，而 right -= x。
    • 若指標從 x=1 到 x=n 遍歷過一次都無解，即傳回 -1，若有解則立即傳回 x。
  • 另外也可以也可以用 Prefix Sum 的概念，同樣從 x=1 到 x=n，找 presum[n] - presum[i] == presum[i+1]。

三、解題

1. Array

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int pivotInteger(int n) {
    if (n == 1) return 1;
    int right = (1 + n) * n/2;
    int left = 1;
    for (int i = 1; i < n; i++) {
        if (left == right) return i;
        left += (i+1);
        right -= i;
    }
    return -1;
}

2. Prefix Sum

  • Time Complexity
int pivotInteger(int n) {
    if (n == 1) return 1;
    vector<int> presum;
    presum.push_back(0);
    for (int i = 1; i <= n; i++) {
        presum.push_back(presum.back() + i);
    }
    for (int i = 1; i < n; i++) {
        if (presum[n] - presum[i] == presum[i+1]) return i+1;
    }
    return -1;
}

回目錄 Catalog