algoadvance

Leetcode 2485. Find the Pivot Integer

Problem Statement:

You are given a positive integer n. The task is to find a pivot integer x that satisfies the following condition: the sum of all integers from 1 to x is equal to the sum of all integers from x to n. If no such x exists, return -1. If multiple such x exist, you can return any of them.

Clarifying Questions:

1. Can n be very large or is there a constraint on the size of n? Typically, we might assume n is within a practical range suitable for medium complexity algorithms, but specific constraints were not provided.
2. Do we need to handle any possible edge cases, such as n = 1? Given n is a positive integer, it’s good to consider all edge cases including the smallest valid n.

Strategy:

1. The sum of integers from 1 to x can be expressed using the formula for the sum of an arithmetic series: S1 = x * (x + 1) / 2.
2. Similarly, the sum of integers from x to n can also be expressed, but this is from x+1 to n plus x: S2 = x + (n * (n + 1) / 2 - x * (x - 1) / 2).
3. Therefore, we need to compute and compare these two expressions to find the pivot point.
4. If the given equation holds for any x in the range 1 to n, we return x. Otherwise, we return -1.

Code:

public class Solution {
    public int pivotInteger(int n) {
        // total sum of all numbers from 1 to n
        int totalSum = (n * (n + 1)) / 2;
        
        // sum from 1 to x should be equal to sum from x to n
        int currentSum = 0;
        for (int x = 1; x <= n; x++) {
            currentSum += x;
            if (currentSum == totalSum - currentSum + x) {
                return x;
            }
        }
        
        return -1; // if no pivot found
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.pivotInteger(8)); // Output will be an integer that satisfies the condition, or -1 if none exists
    }
}

Time Complexity:

The time complexity of this solution is O(n) due to the single loop iterating through all integers from 1 to n. This is efficient given that we are comparing sums within this bounded input range.

Explanation:

• We first calculate the total sum of integers from 1 to n.
• Then, we iterate from 1 to n and calculate the running sum (currentSum).
• At each integer x, we check if currentSum equals the remaining sum (totalSum - currentSum + x).
• If the condition is met, we return x as the pivot integer.
• If no such integer is found after the loop completes, we return -1.

This solution correctly identifies the pivot integer or determines that none exists in linear time, ensuring efficient processing for typical input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?