Problem Statement

Given a strength value p, we need to determine the maximum number of people that can be defeated.

The people stand in an infinite row, and the strength of the person at position i is:

i²

For example, the first few strengths are:

1, 4, 9, 16, 25, ...

A person can only be defeated if the current strength p is greater than or equal to that person's strength. After defeating them, the strength decreases by the amount spent.

Example

Consider:

p = 14

A total of 3 people can be defeated.

Naive Approach

A straightforward approach would be to keep subtracting squares one by one until the remaining strength becomes insufficient.

However, this approach may become inefficient for larger values of p.

Mathematical Observation

To defeat the first n people, the required strength is:

1² + 2² + 3² + ... + n²

This is a well-known mathematical series whose sum is:

n(n + 1)(2n + 1) / 6

Therefore, the problem becomes finding the largest value of n such that:

n(n + 1)(2n + 1) / 6 ≤ p

Why Binary Search Works

Notice that as n increases, the value of:

n(n + 1)(2n + 1) / 6

also increases.

This monotonic behavior makes the problem ideal for Binary Search.

Instead of checking every possible value of n, we search over the answer space.

For a chosen value mid, we calculate:

sum = mid(mid + 1)(2mid + 1) / 6

Case 1: sum ≤ p

Defeating mid people is possible, so we try to find a larger answer.

low = mid + 1

Case 2: sum > p

Defeating mid people is not possible, so we search in the smaller half.

high = mid - 1

The search continues until the maximum valid value of n is found.

Example Walkthrough

Consider:

p = 10

First 2 People

1² + 2²
= 1 + 4
= 5

Since:

5 ≤ 10

defeating 2 people is possible.

First 3 People

1² + 2² + 3²
= 1 + 4 + 9
= 14

Since:

14 > 10

defeating 3 people is not possible.

Therefore, the maximum number of people that can be defeated is:

2

Java Implementation

class Solution {
    int maxPeopleDefeated(int p) {
        long low = 0;
        long high = 10000;

        while (low <= high) {
            long mid = low + (high - low) / 2;

            long sum = mid * (mid + 1) * (2 * mid + 1) / 6;

            if (sum <= p) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return (int) high;
    }
}

Time Complexity

Binary Search repeatedly halves the search space.

O(log n)

Space Complexity

Only a few variables are used throughout the algorithm.

O(1)

Conclusion

Instead of repeatedly subtracting square values one by one, we can transform the problem into a mathematical inequality using the sum of squares formula:

n(n + 1)(2n + 1) / 6 ≤ p

Since the sum of squares grows monotonically, Binary Search can efficiently find the largest valid value of n. This reduces the solution from a potentially linear approach to a logarithmic-time algorithm, making it suitable even for large values of p.