# Find the Pivot Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-pivot-integer)
Canonical: https://scaleengineer.com/dsa/problems/find-the-pivot-integer
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
---
## Problem
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`

# Approaches
## Brute Force with Nested Loops
This is the most straightforward and intuitive approach. We can simply test every possible value for the pivot integer `x` from `1` to `n`. For each candidate `x`, we calculate the sum of all numbers from `1` to `x` and the sum of all numbers from `x` to `n`. If these two sums are equal, we have found our pivot.
**Time:** O(n^2) - The outer loop runs `n` times. For each iteration, the inner loops for calculating `leftSum` and `rightSum` can run up to `n` times, resulting in a time complexity proportional to n*n. · **Space:** O(1) - We only use a few variables to store the sums and loop counters, so the space required is constant.
**Pros:** Very simple to understand and implement.; Correctly solves the problem for the given constraints.
**Cons:** Highly inefficient due to nested loops, leading to a quadratic time complexity.; Will be very slow for large values of `n` and may lead to a 'Time Limit Exceeded' error in competitive programming platforms.
### Explanation
The brute-force method involves a nested loop structure. The outer loop iterates through all possible pivot candidates `x` from `1` to `n`. Inside this loop, two separate inner loops are used. The first inner loop calculates the sum of the elements on the left side of `x` (i.e., from `1` to `x` inclusive). The second inner loop calculates the sum of the elements on the right side (i.e., from `x` to `n` inclusive). After calculating both sums, we compare them. If they are identical, we've found the pivot and can return `x` immediately. If the outer loop finishes without finding any such `x`, we conclude that no pivot exists and return `-1`.

```java
class Solution {
    public int pivotInteger(int n) {
        for (int x = 1; x <= n; x++) {
            int leftSum = 0;
            for (int i = 1; i <= x; i++) {
                leftSum += i;
            }
            
            int rightSum = 0;
            for (int j = x; j <= n; j++) {
                rightSum += j;
            }
            
            if (leftSum == rightSum) {
                return x;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Iterate through each integer `x` from `1` to `n` as a potential pivot.
*   For each `x`, initialize two variables, `leftSum` and `rightSum`, to zero.
*   Calculate `leftSum` by iterating from `1` to `x` and adding each number.
*   Calculate `rightSum` by iterating from `x` to `n` and adding each number.
*   If `leftSum` is equal to `rightSum`, then `x` is the pivot integer. Return `x`.
*   If the loop completes without finding a pivot, it means no such integer exists. Return `-1`.

## Single Pass Iteration
This approach improves upon the brute-force method by optimizing the sum calculations. Instead of recalculating the sums from scratch in each iteration, we can use a running sum for the left side and derive the right side's sum from the total sum. This reduces the complexity from quadratic to linear.
**Time:** O(n) - We iterate through the numbers from 1 to `n` only once, and all operations inside the loop are constant time. · **Space:** O(1) - Constant extra space is used for variables like `totalSum` and `leftSum`.
**Pros:** Significantly more efficient than the O(n^2) brute-force approach.; Still easy to understand and implement.
**Cons:** While much better than the O(n^2) approach, it is still not the most optimal solution.; For extremely large values of `n` (beyond the problem constraints), a linear scan might still be too slow.
### Explanation
We can avoid the nested loops by being smarter about how we calculate the sums. First, we compute the total sum of numbers from 1 to `n` once. Then, we iterate through the potential pivots `x` from `1` to `n`. We maintain a `leftSum` which is the sum of numbers from `1` up to the current `x`. In each step of the loop, we add `x` to `leftSum`. The `rightSum` (sum from `x` to `n`) can then be calculated efficiently as `totalSum - leftSum + x`. We add `x` back because `leftSum` includes `x`, and we want the sum from `x` to `n`, not `x+1` to `n`. We then compare `leftSum` and `rightSum`. This process requires only a single pass through the numbers.

```java
class Solution {
    public int pivotInteger(int n) {
        int totalSum = n * (n + 1) / 2;
        int leftSum = 0;
        for (int x = 1; x <= n; x++) {
            leftSum += x;
            int rightSum = totalSum - leftSum + x;
            if (leftSum == rightSum) {
                return x;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   First, calculate the total sum of numbers from `1` to `n` using the formula `totalSum = n * (n + 1) / 2`.
*   Initialize a variable `leftSum = 0`.
*   Iterate with a variable `x` from `1` to `n`.
*   In each iteration, update `leftSum` by adding the current `x`: `leftSum += x`.
*   The `rightSum` can be derived from `totalSum` and `leftSum`. The sum from `x` to `n` is `totalSum - (sum from 1 to x-1)`. This is equivalent to `totalSum - leftSum + x`.
*   Check if `leftSum == rightSum`. If they are equal, `x` is the pivot. Return `x`.
*   If the loop finishes, no pivot was found. Return `-1`.

## Binary Search
A more efficient approach is to use binary search. We can observe that as the candidate pivot `x` increases, the left sum `(1 + ... + x)` increases and the right sum `(x + ... + n)` decreases. This monotonic property of the difference between the two sums allows us to efficiently search for the pivot.
**Time:** O(log n) - Binary search halves the search space of size `n` in each iteration. · **Space:** O(1) - Only a few variables are needed to keep track of the search boundaries, requiring constant space.
**Pros:** Very efficient with O(log n) time complexity.; Optimal for problems with very large constraints on `n`.
**Cons:** Slightly more complex to conceptualize and implement compared to a linear scan.; The performance gain is only significant for very large `n`.
### Explanation
We can apply binary search on the possible values of `x`, which range from `1` to `n`. For any chosen `mid` value in our search range, we can calculate the left sum and right sum in constant time using the arithmetic series sum formula: `sum(1..k) = k*(k+1)/2`. We compare the two sums. If the left sum is smaller than the right sum, it implies our chosen `mid` is too small, and the actual pivot must be in the right half of the search range. Conversely, if the left sum is larger, the pivot must be in the left half. If the sums are equal, we have found our pivot. This process repeatedly halves the search space, leading to a logarithmic time complexity.

```java
class Solution {
    public int pivotInteger(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int leftSum = mid * (mid + 1) / 2;
            // Sum from x to n is TotalSum - Sum(1 to x-1)
            int rightSum = (n * (n + 1) / 2) - (mid * (mid - 1) / 2);
            
            if (leftSum == rightSum) {
                return mid;
            } else if (leftSum < rightSum) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Define a search range for the pivot `x` from `left = 1` to `right = n`.
*   While `left <= right`:
    *   Calculate the middle element `mid = left + (right - left) / 2`.
    *   Calculate the sum from `1` to `mid` (left sum) using the formula `mid * (mid + 1) / 2`.
    *   Calculate the sum from `mid` to `n` (right sum). This can be found by `(total sum) - (sum from 1 to mid-1)`, which is `(n*(n+1)/2) - (mid*(mid-1)/2)`.
    *   If `leftSum == rightSum`, `mid` is the pivot. Return `mid`.
    *   If `leftSum < rightSum`, the pivot must be larger than `mid`. Adjust the search space to the right half: `left = mid + 1`.
    *   If `leftSum > rightSum`, the pivot must be smaller than `mid`. Adjust the search space to the left half: `right = mid - 1`.
*   If the loop terminates, no pivot was found. Return `-1`.

## Mathematical Solution
The most optimal solution involves reducing the problem to a simple mathematical equation. By expressing the sums on both sides of the pivot condition algebraically, we can solve for `x` directly in terms of `n`.
**Time:** O(1) - The solution involves a handful of arithmetic operations and a square root function, all of which take constant time. · **Space:** O(1) - The calculation requires a fixed number of variables, regardless of the input `n`.
**Pros:** Extremely efficient, providing a solution in constant time.; Elegant and concise.
**Cons:** Requires mathematical derivation which might not be immediately obvious.; Potential for floating-point precision issues if not handled carefully (though using integer arithmetic for the check avoids this).
### Explanation
The condition that the sum of elements from `1` to `x` equals the sum from `x` to `n` can be translated into a mathematical formula. 
Let `S_n` be the sum of integers from `1` to `n`. The condition is `S_x = S_n - S_{x-1}`. 
Substituting the formula for the sum of an arithmetic series, `k(k+1)/2`, we get:
`x(x+1)/2 = n(n+1)/2 - (x-1)x/2`.
Solving this equation for `x` reveals a remarkable simplification: `x^2 = n(n+1)/2`. 
This means that the pivot integer `x` is simply the square root of the total sum of numbers from `1` to `n`. Therefore, the problem reduces to calculating this total sum, finding its square root, and checking if the result is a whole number. If it is, that number is our pivot; otherwise, no integer pivot exists.

```java
class Solution {
    public int pivotInteger(int n) {
        // The condition sum(1..x) == sum(x..n) simplifies to
        // x*x = (n * (n + 1)) / 2
        int totalSum = (n * n + n) / 2;
        int pivot = (int) Math.sqrt(totalSum);
        
        // Check if totalSum is a perfect square
        if (pivot * pivot == totalSum) {
            return pivot;
        }
        
        return -1;
    }
}
```
### Algorithm
*   Start with the pivot condition: `sum(1..x) = sum(x..n)`.
*   Express the sums using the arithmetic series formula: `x*(x+1)/2 = n*(n+1)/2 - (x-1)*x/2`.
*   Simplify the equation algebraically:
    *   `x^2 + x = n^2 + n - (x^2 - x)`
    *   `2*x^2 = n^2 + n`
    *   `x^2 = (n^2 + n) / 2`
*   This means `x` must be the square root of the total sum of numbers from `1` to `n`.
*   Calculate `totalSum = (n*n + n) / 2`.
*   Find the integer square root of `totalSum`. Let's call it `pivot`.
*   Verify if `totalSum` is a perfect square by checking if `pivot * pivot == totalSum`.
*   If it is, `pivot` is the answer. Return `pivot`.
*   Otherwise, no integer pivot exists. Return `-1`.

# Solutions
### Java

```java
class Solution {
public
  int pivotInteger(int n) {
    for (int x = 1; x <= n; ++x) {
      if ((1 + x) * x == (x + n) * (n - x + 1)) {
        return x;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int pivotInteger(int n) {
    for (int x = 1; x <= n; ++x) {
      if ((1 + x) * x == (x + n) * (n - x + 1)) {
        return x;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def pivotInteger(self, n: int) -> int: for x in range(1, n + 1): if (1 + x) * x == (x + n) * (n - x + 1): return x return - 1

```