Maximum Number of People Defeated

Time: O(∛p)

Space: O(1)

Problem Overview

Defeating people 1, 2, …, n costs 1² + 2² + … + n² total power.

Intuition

Defeating people 1, 2, …, n costs 1² + 2² + … + n² total power. Given power budget p, find the largest n such that the sum of squares does not exceed p. Use the closed form n(n+1)(2n+1)/6 ≤ p instead of looping and adding squares.

Algorithm

1Start n = 1 and increment while n(n+1)(2n+1) ≤ 6 * p.
2When the inequality fails, return n - 1.
3Equivalently: largest n with sum of squares 1..n at most p.

Example Walkthrough

Input: p = 14

1. 1² = 1 ≤ 14 → n = 1 OK.
2. 1² + 2² = 5 ≤ 14 → n = 2 OK.
3. 1² + 2² + 3² = 14 ≤ 14 → n = 3 OK.
4. Adding 4² would give 30 > 14 → answer n - 1 = 3.

Output: 3

Common Pitfalls

• Compare n(n+1)(2n+1) to 6*p — multiply p by 6 to avoid fractions.
• Return n - 1 after the loop breaks, not n.
• Use int or long for the cubic check; p can be large.

Maximum Number of People Defeated.java

Java


// Approach: Maximum k such that 1² + 2² + … + k² ≤ p. Use sum-of-squares formula n(n+1)(2n+1)/6.
// Increment n until n(n+1)(2n+1) > 6*p, then return n - 1.
// Time: O(∛p) Space: O(1)
class Solution {

    public int maxPeopleDefeated(int p) {
        int n = 1;
        for (n = 1;; n++) {
            if ((n) * (n + 1) * (2 * n + 1) > 6 * p) {
                break;
            }
        }
        return n - 1;
    }
};

Was this solution helpful?