# 資訊

:::info
- Question: 2485. Find the Pivot Integer
- From: Leetcode Daily Challenge 2024.03.13
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
- Input: `n = 8`
- Output: `6`
- Explanation: `6` is the pivot integer since: `1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21`.
:::

> Example 2:
:::success
- Input: `n = 1`
- Output: `1`
- Explanation: `1` is the pivot integer since: `1 = 1`.
:::

> Example 3:
:::success
- Input: `n = 4`
- Output: `-1`
- Explanation: It can be proved that no such integer exist.
:::

> Constraints:
:::success
- 1 <= n <= 1000
:::

---

# 解法

## 概念

主題是 prefix sum，要解決的問題就是能不能不要從頭到尾每一輪都先算前面和、再算後面和、再比較，因為這樣很慢，其實會發現變動的就是每一輪走到的該值，前面和會加上該值、後面和會減掉該值，用這個想法去做就很快了

不過剛剛寫我用了一個感覺慢一點點點的版本，是每一輪都去算前後和，但並不是一個數字一個數字相加得到的，還是有用比較快的方法去做

## 程式碼

class Solution:
    def pivotInteger(self, n: int) -> int:
        total = ( n * ( 1 + n ) ) / 2
        prefixSum = 0
        for i in range( 1, n+1 ):
            prefixSum += i
            if prefixSum == ( total - prefixSum + i ):
                return i
        return -1

---

# 複雜度

## 時間複雜度

是 $O(n)$，最差就是直接走完整條 list 然後沒找到


## 空間複雜度

是 $O(1)$ 喔！因為只有固定幾個變數而已