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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Pivot Integer

Number: 2571

Difficulty: Easy

Paid? No

Companies: Amazon, Apple

Problem Description

Given a positive integer n, find the pivot integer x such that the sum of the numbers from 1 to x is equal to the sum from x to n. If such an integer exists, return x; otherwise, return -1.

Key Insights

  • The sum from 1 to x can be computed using the formula: x * (x + 1) / 2.
  • The sum from x to n can be computed by taking the total sum from 1 to n and subtracting the sum from 1 to (x-1).
  • Setting these two sums equal leads to an equation that simplifies to: 2 * x^2 = n * (n + 1).
  • Thus, we need to check if n * (n + 1) / 2 is a perfect square, and if so, the square root of that value is the pivot integer.

Space and Time Complexity

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

Solution

We start by computing the total sum from 1 to n using the formula n * (n + 1) / 2. Using the derived relationship, the pivot integer x must satisfy x^2 = n * (n + 1) / 2. We calculate x as the square root of n * (n + 1) / 2. If x is an integer (i.e., x^2 equals n*(n+1)/2), we return x; otherwise, we return -1. This solution uses basic arithmetic operations and a square root function, resulting in constant time and space complexity.

Code Solutions

# Python solution with detailed comments

import math

def pivotInteger(n):
    # Calculate the total sum from 1 to n using the formula for arithmetic series
    total_sum = n * (n + 1) // 2
    # Determine the candidate pivot by taking the square root of half the total sum
    x = int(math.sqrt(total_sum))
    # Check if the square of the candidate equals the computed half of total sum
    if x * x == total_sum:
        return x
    else:
        return -1

# Example usage:
print(pivotInteger(8))  # Output: 6
print(pivotInteger(1))  # Output: 1
print(pivotInteger(4))  # Output: -1
← Back to All Questions