Skip to content

LeetCode: 2485-Find the Pivot Integer 解題紀錄

Last Updated on 2022-11-28 by Clay

題目

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

題目給定一個從 1...n 的公差為 1 的等差數列，而我們要在數列中新增一個數值 x，並且可以讓 1+...+x 剛好等於 x+...+n。

所以 x 這個數值又被稱為 pivot integer。

解題思路

我不太確定有沒有更好的解法，不過基本上我就是把 x=n 一路計算到 x=1（不過在確認 x+...+n 肯定比另外一邊大的時候我就會返回 -1、表示沒有解了），然後過程中兩數列使用等差級數和的公式直接去算有沒有相等。

下面是等差數列和的公式。

其中 a 是初始值、d 是公差、n 是數列的長度。

下面直接來看程式。


C++ 範例程式碼

class Solution {
public:
    int sumArithmeticSeq(int startN, int endN) {
        int n = endN - startN + 1;
        return startN * n + (n * (n - 1) * 1) / 2;
    }
    
    int pivotInteger(int n) {        
        for (int i=n; i>0; --i) {
            int a = sumArithmeticSeq(1, i);
            int b = sumArithmeticSeq(i, n);
            
            // If a < b, there is no answer
            if (a < b) {
                break;
            }
            
            if (a == b) {
                return i;
            }
        }
            
        return -1;
    }
};



Python 範例程式碼

class Solution:
    def sumArithmeticSeq(self, start_n: int, end_n: int) -> int:
        n = end_n - start_n + 1
        return start_n * n + (n * (n - 1) * 1) // 2;
    
    def pivotInteger(self, n: int) -> int:
        for i in reversed(range(1, n+1)):
            a = self.sumArithmeticSeq(1, i)
            b = self.sumArithmeticSeq(i, n)
            
            # If a < b, there is no answer
            if a < b:
                return -1
            elif a == b:
                return i

References

Read More

Tags:

Leave a Reply