Find the Pivot Integer

Difficulty: Easy | Acceptance: 83.80% | Paid: No Topics: Math, Prefix Sum

Given a positive integer n, find the pivot integer x such that:

The sum of all numbers between 1 and x (inclusive) is equal to the sum of all numbers between x and n (inclusive).

Return the pivot integer x. If no such integer exists, return -1.

• Examples
• Constraints
• Brute Force
• Prefix Sum
• Mathematical Formula
• Two Pointers

Examples

Input: n = 8
Output: 6
Explanation: 6 is the pivot integer.
Sum(1, 2, 3, 4, 5, 6) = 21
Sum(6, 7, 8) = 21

Input: n = 1
Output: 1
Explanation: 1 is the pivot integer.
Sum(1) = 1
Sum(1) = 1

Input: n = 4
Output: -1
Explanation: No pivot integer exists.

Constraints

1 <= n <= 1000

Brute Force

Intuition Iterate through each number from 1 to n and check if it’s a pivot by calculating both sums directly.

Steps

• Iterate through each number x from 1 to n
• For each x, calculate sum from 1 to x
• Calculate sum from x to n
• If sums are equal, return x
• If no pivot found, return -1

class Solution:
    def pivotInteger(self, n: int) -> int:
        for x in range(1, n + 1):
            left_sum = sum(range(1, x + 1))
            right_sum = sum(range(x, n + 1))
            if left_sum == right_sum:
                return x
        return -1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large n

Prefix Sum

Intuition Precompute prefix sums to avoid recalculating sums repeatedly, then find the pivot in a single pass.

Steps

• Calculate total sum of all numbers from 1 to n
• Iterate through each number x from 1 to n
• Track running sum from 1 to x
• Check if running sum equals total sum minus running sum plus x
• If equal, return x
• If no pivot found, return -1

class Solution:
    def pivotInteger(self, n: int) -> int:
        total_sum = n * (n + 1) // 2
        left_sum = 0
        for x in range(1, n + 1):
            left_sum += x
            right_sum = total_sum - left_sum + x
            if left_sum == right_sum:
                return x
        return -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Efficient single pass solution

Mathematical Formula

Intuition Use the mathematical property that sum(1 to x) = x(x+1)/2 and derive a formula to directly compute the pivot.

Steps

• Use formula: sum(1 to x) = x(x+1)/2
• Set sum(1 to x) = sum(x to n)
• Derive: x² = n(n+1)/2
• Calculate x = sqrt(n(n+1)/2)
• Check if x is a valid integer pivot
• Return x or -1

import math

class Solution:
    def pivotInteger(self, n: int) -> int:
        total = n * (n + 1) // 2
        x = int(math.isqrt(total))
        if x * x == total:
            return x
        return -1

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Most optimal solution using mathematical derivation

Two Pointers

Intuition Use two pointers starting from both ends, moving towards each other while tracking cumulative sums to find the pivot.

Steps

• Initialize left pointer at 1, right pointer at n
• Track left sum and right sum
• Move the pointer with smaller sum towards center
• When pointers meet, check if sums are equal
• Return the pivot or -1

class Solution:
    def pivotInteger(self, n: int) -> int:
        left, right = 1, n
        left_sum, right_sum = 1, n
        while left < right:
            if left_sum < right_sum:
                left += 1
                left_sum += left
            else:
                right -= 1
                right_sum += right
        return left if left_sum == right_sum else -1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Elegant two-pointer approach