[LeetCode] 2485. Find the Pivot Integer

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