Find the Pivot Integer

EASY

Description

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

Checkout 4 different approaches to solve Find the Pivot Integer. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1) - We only use a few variables to store the sums and loop counters, so the space required is constant.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Pivot Integer. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Find the Pivot Integer

Patterns:

MathPrefix Sum