Find the Pivot Integer - Practice Coding Problems

Find the Pivot Integer - Problem

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.

Note: It is guaranteed that there will be at most one pivot index for the given input.

Input & Output

Example 1 — Basic Case

$ Input: n = 8

› Output: 6

💡 Note: The pivot integer is 6. Sum from 1 to 6: 1+2+3+4+5+6 = 21. Sum from 6 to 8: 6+7+8 = 21. Both sums equal 21.

Example 2 — Single Element

$ Input: n = 1

› Output: 1

💡 Note: The pivot integer is 1. Sum from 1 to 1: 1. Sum from 1 to 1: 1. Both sums equal 1.

Example 3 — No Pivot Exists

$ Input: n = 4

› Output: -1

💡 Note: No pivot exists. For any x: sum(1 to x) ≠ sum(x to 4). Total sum is 10, and √10 ≈ 3.16 is not an integer.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=8, need to find pivot x

Balance Point

Find x where sum(1..x) = sum(x..n)

Output

Return pivot x=6 or -1 if none exists

Key Takeaway

🎯 Key Insight: The pivot condition algebraically simplifies to x² = total_sum, allowing O(1) solution

Asked in

M Microsoft 15 a Amazon 12 G Google 8

The key insight is recognizing that the pivot condition sum(1 to x) = sum(x to n) simplifies to x² = total_sum. Best approach is the mathematical formula with direct square root calculation. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula (Optimal)	O(1)	O(1)	Use algebra to derive a direct formula for the pivot
Brute Force - Check Every Possible Pivot	O(n²)	O(1)	Try each number from 1 to n and calculate both sums
Prefix Sum Optimization	O(n)	O(1)	Use running sums to avoid recalculating sums repeatedly

Mathematical Formula (Optimal) — Algorithm Steps

Calculate total sum from 1 to n using n*(n+1)/2
Calculate square root of total sum
Check if the square root is a perfect integer
If yes and within bounds [1,n], return it; otherwise return -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Derive Formula

sum(1 to x) = sum(x to n) → x² = total_sum

Calculate

total_sum = 36, x = √36 = 6

Verify

6² = 36 ✓ and 1 ≤ 6 ≤ 8 ✓

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int solution(int n) {
    long long totalSum = (long long) n * (n + 1) / 2;
    int x = (int) sqrt(totalSum);
    
    // Check if x is a perfect square root and within bounds
    if ((long long) x * x == totalSum && x >= 1 && x <= n) {
        return x;
    }
    
    return -1;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Single square root calculation and integer check

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables for calculations

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler