LeetCode Problem 2485

Difficulty: 🟢 Easy
Topics: Math, Prefix Sum

Solution

LeetCode 2485 - Find the Pivot Integer

Problem Understanding

The problem gives us a positive integer n and asks us to find a special integer x, called the pivot integer, such that:

• The sum of all integers from 1 to x is equal to
• The sum of all integers from x to n

The important detail is that x belongs to both sums. In other words:

$$1 + 2 + \dots + x = x + (x+1) + \dots + n$$

We need to return the value of x if such an integer exists. If no such integer exists, we return -1.

The input consists of a single integer n, where:

$$1 \le n \le 1000$$

This constraint is very small, which means even less efficient approaches could work within time limits. However, the problem is primarily about recognizing the mathematical relationship that allows a cleaner and more optimal solution.

The problem also guarantees that there is at most one valid pivot integer. This means we never need to worry about multiple answers or deciding between them.

Several edge cases are important:

• When n = 1, the only number is both the left and right sum, so the answer is 1.
• Some values of n do not produce any pivot integer at all, such as n = 4.
• Since the sums grow quickly, we should be careful about correctly handling the overlapping pivot value in both ranges.

Approaches

Brute Force Approach

The most direct approach is to try every possible pivot integer from 1 to n.

For each candidate x:

• Compute the sum from 1 to x
• Compute the sum from x to n
• Compare the two sums

If they are equal, return x.

This approach is correct because it explicitly checks every possible pivot integer and verifies the required condition exactly as stated in the problem.

However, this solution repeatedly recomputes sums for every candidate. If we calculate each sum using loops, then for every x we may perform up to O(n) work. Since there are n possible pivot values, the total complexity becomes O(n²).

Even though n <= 1000 makes this feasible, we can do much better.

Optimal Mathematical Approach

The key observation comes from using the formula for the sum of the first n integers.

The total sum from 1 to n is:

$1+2+\cdots+n=\frac{n(n+1)}{2}$

Suppose x is the pivot integer.

The left side sum is:

$$1 + 2 + \dots + x$$

The right side sum is:

$$x + (x+1) + \dots + n$$

Since both sums are equal, and together they cover the entire range with x counted twice, we can derive:

$$\text{left sum} = \text{total sum} - \text{left sum} + x$$

Let:

$$S = \frac{n(n+1)}{2}$$

and:

$$\text{left sum} = \frac{x(x+1)}{2}$$

Substituting:

$$\frac{x(x+1)}{2} = S - \frac{x(x+1)}{2} + x$$

After simplification, we get:

$x^2=\frac{n(n+1)}{2}$

This means the pivot integer exists only if the total sum is a perfect square.

So the algorithm becomes:

1. Compute the total sum.
2. Compute its integer square root.
3. If the square of that root equals the total sum, return the root.
4. Otherwise return -1.

This reduces the time complexity to O(1).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every candidate and recomputes sums repeatedly
Optimal	O(1)	O(1)	Uses mathematical derivation and perfect square check

Algorithm Walkthrough

1. Compute the total sum of integers from 1 to n.

We use the arithmetic series formula:

$$\text{total} = \frac{n(n+1)}{2}$$

This avoids looping through the numbers. 2. Compute the integer square root of the total sum.

If a pivot integer exists, then:

$$x^2 = \text{total}$$

Therefore, the pivot integer must be the square root of the total sum. 3. Verify whether the total sum is a perfect square.

We compute:

$$\text{root} \times \text{root}$$

If this equals the total sum exactly, then root is the pivot integer. 4. Return the result.

• If the total sum is a perfect square, return root.
• Otherwise return -1.

Why it works

The correctness comes directly from the equality condition between the two ranges. By expressing both sums mathematically and simplifying the equation, we prove that a pivot integer exists if and only if the total sum from 1 to n is a perfect square. Therefore, checking for a perfect square is sufficient and guarantees the correct answer.

Python Solution

import math

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

The implementation begins by computing the total sum from 1 to n using the arithmetic series formula. This avoids iteration and gives the result in constant time.

Next, math.isqrt() computes the integer square root safely and efficiently. Unlike floating point square roots, integer square roots avoid precision issues.

The code then checks whether the square of the computed root equals the total sum exactly. If it does, the total sum is a perfect square, and the root is the pivot integer.

If the condition fails, no valid pivot integer exists, so the function returns -1.

Go Solution

package main

import "math"

func pivotInteger(n int) int {
    totalSum := n * (n + 1) / 2

    root := int(math.Sqrt(float64(totalSum)))

    if root*root == totalSum {
        return root
    }

    return -1
}

The Go implementation follows the same mathematical logic as the Python version.

One small difference is that Go does not provide an integer square root function in the standard library like Python's math.isqrt(). Instead, we use math.Sqrt() with a float64 conversion and then cast the result back to an integer.

Since the constraints are very small, floating point precision is not a concern here.

Worked Examples

Example 1

Input:

n = 8

First compute the total sum:

Calculation	Value
8 * 9 / 2	36

Now compute the square root:

Variable	Value
root	6

Verification:

Check	Result
6 * 6 == 36	True

Return:

6

Validation:

Left Sum	Right Sum
1 + 2 + 3 + 4 + 5 + 6 = 21	6 + 7 + 8 = 21

Example 2

Input:

n = 1

Compute total sum:

Calculation	Value
1 * 2 / 2	1

Square root:

Variable	Value
root	1

Verification:

Check	Result
1 * 1 == 1	True

Return:

1

Example 3

Input:

n = 4

Compute total sum:

Calculation	Value
4 * 5 / 2	10

Square root:

Variable	Value
root	3

Verification:

Check	Result
3 * 3 == 10	False

Return:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations and a square root calculation are performed
Space	O(1)	No additional data structures are used

The algorithm performs a constant number of operations regardless of the value of n. Since the computation does not scale with input size, both time and space complexities remain constant.

Test Cases

solution = Solution()

assert solution.pivotInteger(8) == 6      # standard valid pivot case
assert solution.pivotInteger(1) == 1      # smallest possible input
assert solution.pivotInteger(4) == -1     # no valid pivot exists
assert solution.pivotInteger(49) == 35    # larger valid pivot
assert solution.pivotInteger(2) == -1     # small invalid case
assert solution.pivotInteger(3) == -1     # another no-solution case
assert solution.pivotInteger(288) == 204  # large valid perfect square case
assert solution.pivotInteger(1000) == -1  # upper constraint boundary

Test	Why
n = 8	Verifies standard successful case
n = 1	Tests minimum boundary value
n = 4	Verifies correct handling when no pivot exists
n = 49	Tests a larger valid pivot integer
n = 2	Small input without a solution
n = 3	Another invalid configuration
n = 288	Large valid case where total sum is a perfect square
n = 1000	Tests upper input boundary

Edge Cases

Edge Case 1: Minimum Input Value

When n = 1, the range contains only one number. Both the left and right sums are simply 1, so the pivot integer exists and equals 1.

This case is important because some implementations incorrectly assume both sides must contain multiple elements. The mathematical derivation naturally handles this case correctly because:

$$\frac{1(1+1)}{2} = 1$$

which is a perfect square.

Edge Case 2: No Valid Pivot Integer

Many values of n do not produce any pivot integer. For example:

n = 4

The total sum is:

$$10$$

Since 10 is not a perfect square, no integer x can satisfy the condition.

A buggy implementation might incorrectly round square roots or use floating point comparisons carelessly. The implementation avoids this by verifying:

root * root == total_sum

exactly.

Edge Case 3: Large Boundary Values

The largest possible input is:

n = 1000

Even though the constraints are small, boundary testing is still important. The total sum remains well within integer limits:

$$\frac{1000 \times 1001}{2} = 500500$$

The implementation uses integer arithmetic throughout, so there are no overflow issues in either Python or Go under the given constraints.