Leetcode-Find-the-Pivot-Integer

Leetcode 2485. Find the Pivot Integer 解題心得

題目: 2485. Find the Pivot Integer

題目描述

給定一個正整數 n，找出一個整數 x，使得 1 到 x 的總和等於 x 到 n 的總和。

如果找不到這樣的 x，則回傳 -1。

解題思路

這題可以有三種解法：

• 暴力法
• 分半法
• 數學法

暴力法

暴力法就是從 1 開始，一個一個試，直到找到答案為止。

class Solution:
    def pivotInteger(self, n: int) -> int:
        s1 = 0
        s2 = 0
        for i in range(1,n+1):
            s1 = sum(range(1, i+1))
            s2 = sum(range(i, n+1))
            if(s1==s2):
                return i
        return -1

分半法

分半法就是從 n/2 開始，看兩邊的總和是否相等，如果不相等，就往總和大的那邊移動，直到找到答案為止。

class Solution:
    def pivotInteger(self, n: int) -> int:
        x = int(n/2)
        flag = 0
        num_table = [t for t in range(1,n+1)]
        x_record = []
        while x<n and x >= 0 and x not in x_record:
            x_record.append(x)
            a_part , b_part = sum(num_table[:x+1]) , sum(num_table[x:])
            if a_part == b_part:
                flag = 1
                break
            if a_part < b_part:x=x+1
            if a_part > b_part:x=x-1
        return x+1 if flag else -1

數學法

這題其實可以用數學的方式解，因為 1 到 n 的總和是可以用公式算出來的，所以只要把公式帶入，就可以得到答案。

公式推導可以參考這裡。

class Solution:
    def pivotInteger(self, n: int) -> int:
        '''
        x=( n(n+1)/2   )**0.5
        n*(n+1)//2 must be a squared number
        8*(8+1)//2=36
        1*(1+1)//2=1
        '''
        tar=n*(n+1)//2
        r=int(tar**0.5)
        return r if r*r==tar else -1