Perfect Squares

📋

Problem

Imagine you want to represent a number as a sum of perfect squares, like breaking a chocolate bar into square pieces with minimal cuts.

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer (e.g., 1, 4, 9, 16, ...). Input: integer n. Output: integer representing the minimum count of perfect squares summing to n.

1 ≤ n ≤ 10^5

Edge cases: n = 1 → output 1 (smallest input)n = 0 → output 0 (no squares needed)n = 10000 → output 1 (perfect square itself)

</>

IDE

def numSquares(n: int) -> int:public int numSquares(int n)int numSquares(int n)function numSquares(n)

def numSquares(n):
    # Write your solution here
    pass

class Solution {
    public int numSquares(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int numSquares(int n) {
    // Write your solution here
    return 0;
}

function numSquares(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Greedy approach picking largest square once, ignoring multiple usage.✅ Iterate over all squares j*j <= i and update dp[i] = min(dp[i], 1 + dp[i - j*j]) allowing repeated use.

Wrong: 3Confusing 0/1 knapsack with unbounded knapsack, using each square only once.✅ Allow multiple usage by using unbounded knapsack recurrence: dp[i] = min(dp[i], 1 + dp[i - j*j]) for all j.

Wrong: 0Missing base case for n=0 or incorrect initialization.✅ Set dp[0] = 0 explicitly to handle zero input correctly.

Wrong: 2Off-by-one error in dp array indexing or incomplete iteration.✅ Ensure dp array covers all indices from 0 to n inclusive and loops run correctly.

Wrong: TLEUsing brute force recursion without memoization or bottom-up DP.✅ Implement bottom-up DP with precomputed squares to achieve O(n * sqrt(n)) time.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Beware of greedy and 0/1 knapsack mistakes; remember unbounded usage.

Optimize your DP to handle large inputs efficiently.

t1_01basic

Input{"n":12}

Expected3

⏱ Performance - must finish in 2000ms

12 = 4 + 4 + 4 (three perfect squares)

💡 Think about representing n as sum of squares with minimal count.

💡 Use dynamic programming with states representing minimum squares for each number.

💡 dp[i] = min(dp[i], 1 + dp[i - j*j]) for all j*j <= i.

Why it failed: Returned wrong count for n=12; likely missed checking all squares up to sqrt(n). Fix by iterating over all j where j*j <= i in dp.

✓ Correctly computed minimum squares for n=12.

t1_02basic

Input{"n":13}

Expected2

⏱ Performance - must finish in 2000ms

13 = 4 + 9 (two perfect squares)

💡 Try building solution bottom-up from smaller numbers.

💡 Check all perfect squares less than or equal to current number.

💡 Update dp[i] = min(dp[i], 1 + dp[i - j*j]) for all valid j.

Why it failed: Incorrect result for n=13; possibly only considered one square or greedy approach. Fix by considering all squares up to sqrt(i) for each i.

✓ Correctly found minimal squares sum for n=13.

t2_01edge

Input{"n":0}

Expected0

⏱ Performance - must finish in 2000ms

No squares needed to sum to zero.

💡 Consider base case when n=0.

💡 dp[0] should be initialized to 0 since no squares are needed.

💡 Ensure your code handles n=0 without errors and returns 0.

Why it failed: Returned non-zero for n=0; base case missing or incorrect initialization. Fix by setting dp[0] = 0 explicitly.

✓ Correctly handled zero input base case.

t2_02edge

Input{"n":1}

Expected1

⏱ Performance - must finish in 2000ms

1 = 1 (one perfect square)

💡 Check smallest positive input n=1.

💡 dp[1] should be 1 since 1 itself is a perfect square.

💡 Make sure dp array or memo returns 1 for n=1.

Why it failed: Returned incorrect count for n=1; possibly dp initialization or iteration off by one. Fix by ensuring dp[1] = 1.

✓ Correctly computed minimal squares for n=1.

t2_03edge

Input{"n":10000}

Expected1

⏱ Performance - must finish in 2000ms

10000 = 100^2 (one perfect square)

💡 Check large perfect square input.

💡 If n is a perfect square, answer is 1 immediately.

💡 Add a quick check for perfect squares before DP to optimize.

Why it failed: Returned more than 1 for perfect square input n=10000; missed direct perfect square check. Fix by adding isPerfectSquare shortcut.

✓ Correctly identified perfect square input with answer 1.

t3_01corner

Input{"n":2}

Expected2

⏱ Performance - must finish in 2000ms

2 = 1 + 1 (two perfect squares)

💡 Beware of greedy approach picking largest square first.

💡 Try all squares less than or equal to current number, not just largest.

💡 dp[i] = min over all j*j <= i of 1 + dp[i - j*j].

Why it failed: Returned 1 for n=2 due to greedy picking 1^2 once; missed multiple usage. Fix by allowing repeated use of squares in dp.

✓ Correctly handled unbounded usage of squares for n=2.

t3_02corner

Input{"n":7}

Expected4

⏱ Performance - must finish in 2000ms

7 = 4 + 1 + 1 + 1 (four perfect squares)

💡 Check that your solution does not confuse 0/1 knapsack with unbounded knapsack.

💡 You can use each square multiple times.

💡 Ensure dp recurrence allows repeated squares: dp[i] = min(dp[i], 1 + dp[i - j*j]).

Why it failed: Returned 3 for n=7 by using each square once only; violates unbounded constraint. Fix dp to allow multiple usage of squares.

✓ Correctly implemented unbounded knapsack logic for n=7.

t3_03corner

Input{"n":23}

Expected4

⏱ Performance - must finish in 2000ms

23 = 9 + 9 + 4 + 1 (four perfect squares)

💡 Watch for off-by-one errors in dp indexing.

💡 Make sure dp array covers all indices up to n inclusive.

💡 Initialize dp with large values and update correctly for all i from 1 to n.

Why it failed: Returned incorrect count for n=23 due to off-by-one or incomplete dp iteration. Fix by iterating dp from 1 to n inclusive.

✓ Correctly computed minimal squares for n=23 with full dp coverage.

t4_01performance

Input{"n":100000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, O(n * sqrt(n)) DP must complete within 2 seconds.

💡 Optimize by precomputing all perfect squares up to n.

💡 Use bottom-up DP with O(n * sqrt(n)) complexity.

💡 Avoid recursion or exponential brute force to prevent TLE.

Why it failed: TLE due to exponential or non-optimized approach. Fix by implementing bottom-up DP with precomputed squares.

✓ Efficient DP solution runs within time limits for n=100000.

Practice

1. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?

easy

A. 1

B. 3

C. 0

D. 2

Solution

1. Step 1: Trace initial dp array

   total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)

2. Step 2: Process num=1 and num=2 updating dp

   After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two ways: +1-2 and -1+2 sum to 1 [OK]

Hint: Offset indexing maps sums to dp indices [OK]

Common Mistakes:

• Off-by-one errors in indexing dp array

2. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?

medium

A. Line 5: inner loop iterating backwards over amounts

B. Line 4: outer loop over coins

C. Line 2: dp initialization

D. Line 6: updating dp[w] with dp[w - coin]

Solution

1. Step 1: Understand iteration order effect

   Iterating amounts backwards causes dp to count permutations, not combinations.

2. Step 2: Identify bug line

   Line 5 iterates w from amount down to coin, which breaks combination counting logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration over amounts is required to count combinations correctly [OK]

Hint: Check direction of inner loop iteration [OK]

Common Mistakes:

• Using backward iteration in 1D dp
• Misplacing dp[0] initialization

3. What is the time complexity of the bottom-up dynamic programming solution for the integer break problem shown below?

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

medium

A. O(n log n) time

B. O(n) time

C. O(2^n) time

D. O(n^2) time

Solution

1. Step 1: Identify loops

   Outer loop runs from 2 to n (≈ n iterations). Inner loop runs from 1 to i (up to n iterations).

2. Step 2: Calculate total operations

   Nested loops yield roughly 1 + 2 + ... + n ≈ n(n+1)/2 = O(n^2) operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Double nested loops with linear bounds -> quadratic time [OK]

Hint: Nested loops with linear bounds usually mean O(n²) [OK]

Common Mistakes:

• Confusing with O(n) by ignoring inner loop
• Thinking recursion stack adds exponential time here

4. Suppose the problem is modified so that each coin can be used at most once (0/1 knapsack variant). Which of the following changes to the original code correctly counts the number of combinations?

hard

A. Change inner loop to iterate amounts backward (from amount down to coin) to avoid reuse

B. Change inner loop to iterate amounts forward (from coin to amount) as in original code

C. Use recursion without memoization to explore all subsets

D. Use greedy approach picking largest coins first

Solution

1. Step 1: Understand 0/1 knapsack constraints

   Each coin can be used once, so dp updates must avoid reuse within same iteration.

2. Step 2: Identify correct iteration order

   Iterating amounts backward ensures dp[w] uses dp[w - coin] from previous iteration, preventing reuse.

3. Step 3: Evaluate other options

   Forward iteration allows reuse; recursion without memoization is inefficient; greedy is incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backward iteration is standard for 0/1 knapsack to avoid reuse [OK]

Hint: Backward iteration prevents reuse in 0/1 knapsack [OK]

Common Mistakes:

• Using forward iteration causing reuse
• Relying on greedy or naive recursion

5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?

hard

A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner

B. Sort coins and greedily pick largest coins without repetition until amount is reached

C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)

D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

1. Step 1: Understand the 0/1 usage constraint

   Each coin can be used once, so we must track usage per coin, requiring 2D dp.

2. Step 2: Identify correct DP structure

   2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.

3. Step 3: Why other options fail

   Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   0/1 knapsack requires 2D dp to track coin usage [OK]

Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]

Common Mistakes:

• Using unbounded knapsack DP for 0/1 problem
• Assuming greedy works for minimum coins