We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Pivot Integer

Difficulty: Easy

Problem 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.

Key Insights

  • The pivot integer x must satisfy the equation: sum(1 to x) = sum(x to n).
  • The sum of the first k natural numbers can be computed using the formula: sum(1 to k) = k * (k + 1) / 2.
  • Rearranging the equation leads to a quadratic equation in terms of x.
  • The solution can be found in O(1) time using mathematical manipulation.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To find the pivot integer x, we can use the formula for the sum of the first k natural numbers. The equation can be reformulated as follows:

  1. Calculate the total sum from 1 to n using the formula: total_sum = n * (n + 1) / 2.
  2. Then, set up the equation: x * (x + 1) / 2 = total_sum - (x * (x + 1) / 2).
  3. Simplify the equation to derive a quadratic equation in x.
  4. Solve the quadratic equation and check if the solution is a positive integer within the bounds of 1 and n.

This approach uses basic arithmetic and algebra to derive the answer without the need for complex data structures.

Code Solutions

def findPivotInteger(n):
    total_sum = n * (n + 1) // 2
    x = int((total_sum**0.5))
    if x * (x + 1) // 2 == total_sum - (x * (x + 1) // 2):
        return x
    return -1
← Back to All Questions