Natural Sum

Problem Link - Natural Sum

Problem: Find `s` such that Sum of First `s` Natural Numbers is `N`

Problem Statement

Given an integer N, find the number s such that the sum of the first s natural numbers equals N.

The sum of the first s natural numbers is given by the formula:

$S u m = \frac{s \cdot (s + 1)}{2}$

You need to find such an s that:

$\frac{s \cdot (s + 1)}{2} = N$

If no such s exists, return -1.

Examples

Example 1
Input: N = 10
Output: 4
Explanation: 1+2+3+4=101 + 2 + 3 + 4 = 10

Example 2
Input: N = 17
Output: -1
Explanation: No such s exists where the sum equals 17.

Constraints

Expected Time Complexity: O(log⁡N)
Expected Space Complexity: O(1)

Intuition

The sum of the first s natural numbers increases monotonically as s increases. This allows us to use binary search to efficiently find the value of s.

We search for s in the range 1 to N, and compute the sum for each mid-point using the formula:

$c o m p = \frac{m \cdot (m + 1)}{2}$

If comp == N, we return m. If comp > N, the answer must be smaller, so we move the end to m - 1. If comp < N, we move the start to m + 1.

Approach

Use binary search between s = 1 and s = N.
At each step, calculate the sum of the first m natural numbers using the formula.
Compare the computed sum to N.
Adjust the search space based on comparison.
If a matching s is found, return it; otherwise, return -1.

Code (Java)

class Solution {
    public int find(int n) {
        int s = 0;
        int e = n;
        while (s <= e) {
            int m = s + (e - s) / 2;
            long comp = ((long) m * (m + 1)) / 2;
            if (comp == n) return m;
            else if (comp > n) e = m - 1;
            else s = m + 1;
        }
        return -1;
    }
}

Time and Space Complexity

Time Complexity: O(log⁡N)
Because binary search is used to find the correct value of s.
Space Complexity: O(1)
Only a constant amount of extra space is used.

Dry Run

Input: `N = 10`

Start: s = 0, e = 10
Mid: m = 5 → sum = 5 * 6 / 2 = 15 → too high → e = 4
Mid: m = 2 → sum = 2 * 3 / 2 = 3 → too low → s = 3
Mid: m = 3 → sum = 3 * 4 / 2 = 6 → too low → s = 4
Mid: m = 4 → sum = 4 * 5 / 2 = 10 → match → return 4

Input: `N = 17`

Start: s = 0, e = 17
Mid: m = 8 → sum = 8 * 9 / 2 = 36 → too high → e = 7
Mid: m = 3 → sum = 3 * 4 / 2 = 6 → too low → s = 4
Mid: m = 5 → sum = 5 * 6 / 2 = 15 → too low → s = 6
Mid: m = 6 → sum = 6 * 7 / 2 = 21 → too high → e = 5
s > e → no valid s → return -1

Conclusion

This problem leverages the mathematical formula for the sum of the first s natural numbers and applies binary search for optimal performance. It's a classic application of numerical search over a monotonic function.

Problem: Find s such that Sum of First s Natural Numbers is N