Bird
Raised Fist0
Interview Prepdp-knapsackmediumGoogleAmazon

Perfect Squares

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"n":12}
Expected3

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

t1_02basic
Input{"n":13}
Expected2

13 = 4 + 9 (two perfect squares)

t2_01edge
Input{"n":0}
Expected0

No squares needed to sum to zero.

t2_02edge
Input{"n":1}
Expected1

1 = 1 (one perfect square)

t2_03edge
Input{"n":10000}
Expected1

10000 = 100^2 (one perfect square)

t3_01corner
Input{"n":2}
Expected2

2 = 1 + 1 (two perfect squares)

t3_02corner
Input{"n":7}
Expected4

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

t3_03corner
Input{"n":23}
Expected4

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

t4_01performance
Input{"n":100000}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Greedy algorithm that repeatedly picks the largest element and tries to fit it into subsets
B. Dynamic programming with bitmask tabulation that tracks subset sums for all combinations
C. Simple backtracking without memoization that tries all possible assignments
D. Sorting the array and using a two-pointer technique to pair elements

Solution

  1. Step 1: Understand problem constraints

    The problem requires partitioning into equal sum subsets, which is a classic NP-complete problem requiring exploration of subsets.
  2. Step 2: Identify algorithmic pattern

    Dynamic programming with bitmask tabulation efficiently explores all subsets and tracks partial sums modulo target, guaranteeing optimality.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Bitmask DP covers all subsets systematically [OK]
Hint: Bitmask DP tracks all subset sums efficiently [OK]
Common Mistakes:
  • Assuming greedy always works for equal sum partition
  • Using backtracking without memoization leads to timeouts
2. The following code attempts to solve the minimum subset sum difference problem using space-optimized DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 4: dp initialization without dp[0] = true
B. Line 6: Outer loop iterating over elements
C. Line 7: Inner loop iterating backwards from total_sum
D. Line 11: Returning difference using total_sum and w

Solution

  1. Step 1: Check base case initialization

    dp[0] must be true to represent sum zero achievable with empty subset; missing this causes no sums to be marked achievable.
  2. Step 2: Verify other lines

    Loops and return statement are correct; only missing dp[0] initialization breaks correctness.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without dp[0] = true, dp array never updates correctly [OK]
Hint: dp[0] = true is essential base case [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Using forward iteration causing overcounting
3. What is the time complexity of the optimal bottom-up dynamic programming solution for the problem, given strs has length l, and the constraints are m zeros and n ones?
medium
A. O(l * (m + n))
B. O(l * m * n)
C. O(l * m * n * max_length_of_string)
D. O(2^l)

Solution

  1. Step 1: Identify loops in the code

    Outer loop iterates over all strings (l), inner loops iterate over m and n capacities.
  2. Step 2: Calculate total operations

    Each string causes updates over a 2D dp array of size (m+1)*(n+1), so total complexity is O(l * m * n).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nested loops over l, m, n -> O(l * m * n) [OK]
Hint: Nested loops over strings and both capacities multiply complexities [OK]
Common Mistakes:
  • Confusing sum with product of m and n
  • Including string length in complexity unnecessarily
4. Examine the following code snippet which attempts to solve the problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.
medium
A. Line 7: zeros = s.count('0')
B. Line 10: for j in range(0, n - ones + 1):
C. Line 9: for i in range(0, m - zeros + 1): # iterating forwards
D. Line 11: dp[i + zeros][j + ones] = max(dp[i + zeros][j + ones], 1 + dp[i][j])

Solution

  1. Step 1: Understand dp iteration direction

    To avoid counting the same string multiple times, dp must be updated backwards (from high to low indices).
  2. Step 2: Identify bug in iteration

    Iterating forwards over i and j causes dp states to be reused within the same iteration, leading to overcounting.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Backward iteration is required for 0/1 knapsack variants [OK]
Hint: Forward iteration in 0/1 knapsack dp causes double counting [OK]
Common Mistakes:
  • Forgetting to iterate dp backwards
  • Miscounting zeros and ones
5. Suppose the Target Sum problem is modified so that each number in the array can be used multiple times (unlimited reuse). Which of the following changes correctly adapts the DP solution to this variant?
hard
A. Use a 1D dp array and update dp in forward order for each num to allow reuse
B. Keep the same DP with offset and update dp in reverse order to avoid double counting
C. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num]
D. Switch to a brute force recursion since DP cannot handle reuse

Solution

  1. Step 1: Understand reuse impact on DP iteration

    Allowing unlimited reuse means for each num, dp must be updated in forward order so that dp[s-num] includes ways using current num multiple times.
  2. Step 2: Identify correct DP update order

    Backward iteration prevents reuse by only using previous states. Forward iteration accumulates counts correctly for unlimited usage.
  3. Step 3: Evaluate options

    Use a 1D dp array and update dp in forward order for each num to allow reuse correctly updates dp forward. Keep the same DP with offset and update dp in reverse order to avoid double counting backward iteration is for no reuse. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num] restricts to previous items only. Switch to a brute force recursion since DP cannot handle reuse is inefficient.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward dp update enables multiple usage of same number [OK]
Hint: Forward dp iteration enables unlimited reuse [OK]
Common Mistakes:
  • Using backward iteration which forbids reuse
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard