algoadvance

Leetcode 2485. Find the Pivot Integer

Problem Statement

We are given a positive integer n, which is the range limit starting from 1. We need to find the “pivot integer” x such that the sum of all integers from 1 to x is equal to the sum of all integers from x to n. Formally, find x such that:

[ \sum_{i=1}^{x} i = \sum_{i=x}^{n} i ]

If such a x exists, return it; otherwise, return -1.

Clarifying Questions

  1. Is n guaranteed to be a positive integer?
  2. What is the maximum value for n? (This helps in understanding the range of inputs and possible optimization steps)
  3. Should the solution consider any valid integer, or do we have to check for edge cases such as n = 1?
  4. What should be the output if there are multiple pivot integers?

Strategy

The key to solving the problem is recognizing the properties of series summations and leveraging mathematical formulas to simplify the computation. Let’s formulate the equations:

  1. Sum from 1 to x: [ S_1 = \frac{x (x + 1)}{2} ]

  2. Sum from x to n: [ S_2 = \frac{n (n + 1)}{2} - \frac{x (x - 1)}{2} ]

We need to find an x such that: [ S_1 = S_2 ]

Expanding and simplifying: [ \frac{x (x + 1)}{2} = \frac{n (n + 1)}{2} - \frac{x (x - 1)}{2} ]

Multiplying through by 2 to clear the denominators: [ x (x + 1) = n (n + 1) - x (x - 1) ]

Simplifying the terms: [ x^2 + x = n^2 + n - x^2 + x ]

Reorganizing terms and combining like terms: [ 2x^2 = n^2 + n ]

Therefore, this translates into solving for x: [ x^2 = \frac{n^2 + n}{2} ] [ x = \sqrt{\frac{n^2 + n}{2}} ]

So, we need to check if x computed above is a valid integer that falls within the range [1, n].

Code

#include <cmath>
#include <iostream>

int findPivot(int n) {
    // Calculate the potential pivot integer
    double sum = (n * (n + 1.0)) / 2.0;
    double x = sqrt(sum);
    
    // Check if x is an integer and also within the range [1, n]
    if (x == static_cast<int>(x) && x >= 1 && x <= n) {
        return static_cast<int>(x);
    }
    
    // If no valid pivot integer is found
    return -1;
}

int main() {
    int n = 8;
    std::cout << "Pivot integer for n = " << n << " is: " << findPivot(n) << std::endl;
    return 0;
}

Time Complexity

Thus, the overall time complexity for this approach is ( O(1) ).

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