Jobs

Interviews

Discussions

Perfect Squares

Medium

Revolut

1 view

Topics:

Dynamic Programming

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; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10⁴

Try coding it in LeetCode

Perfect Squares

Medium

Revolut

1 view

Topics:

Dynamic Programming

Given an integer n, return the least number of perfect square numbers that sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer `n`? This will help me consider potential memory usage and algorithm efficiency.
Is `n` guaranteed to be a positive integer, or do I need to handle cases where `n` is zero or negative?
If `n` cannot be represented as a sum of perfect squares, what should the return value be? Is there an error code or a specific default value I should return?
Are we looking for *any* combination of perfect squares that sums to `n`, or should I prioritize using a smaller number of *distinct* perfect squares if multiple solutions with the same count exist?
Can you provide a few example inputs and expected outputs to further clarify the problem and expected behavior?

Brute Force Solution

Approach

Imagine you have a number, and you want to find the fewest perfect squares that add up to it. The brute force method is like trying every possible combination of perfect squares to see if they sum up to your number.

Here's how the algorithm would work step-by-step:

Start by listing all perfect squares smaller than or equal to the number you are trying to reach.
Try using just one of those perfect squares to see if it equals your number. If so, you're done!
If not, try all possible pairs of perfect squares from your list and see if any of the pairs add up to your number. If you find one, great!
If no pair works, move on to trying all possible combinations of three perfect squares, and so on.
Continue adding more perfect squares in your combinations until you find a combination that adds up to your number.
As you find valid combinations, keep track of how many perfect squares each combination uses.
Finally, pick the combination that uses the fewest perfect squares; that's your answer!

Code Implementation

def perfect_squares_brute_force(number):
    # Generate perfect squares less than or equal to the input number
    perfect_squares = [square**2 for square in range(1, int(number**0.5) + 1)]

    if number in perfect_squares:
        return 1

    # Iterate through possible number of perfect squares
    for num_squares in range(2, number + 1): 
        # Try combinations of perfect squares
        combinations = find_combinations(number, num_squares, perfect_squares)
        if combinations:
            return num_squares

    return number

def find_combinations(target_number, num_squares, perfect_squares):
    if num_squares == 0:
        return target_number == 0
    if target_number < 0:
        return False

    # Check all possible combinations with recursion
    for perfect_square in perfect_squares:
        if find_combinations(target_number - perfect_square, num_squares - 1, perfect_squares):
            return True

    return False

def num_squares(number):
    # Handle edge case for non-positive numbers
    if number <= 0:
        return 0

    # Use brute force method to find fewest perfect squares
    return perfect_squares_brute_force(number)

Big(O) Analysis

Time Complexity

O(n^sqrt(n)) – The brute force approach, as described, first generates a list of perfect squares less than or equal to the input number n. There are approximately sqrt(n) such perfect squares. The algorithm then iterates through combinations of these perfect squares. In the worst case, it could potentially check all combinations of up to sqrt(n) perfect squares. This leads to a time complexity of O(n^sqrt(n)), as the number of combinations grows exponentially with the number of perfect squares allowed in each combination, where the maximum perfect squares in a combination is bounded by sqrt(n) in the worst case. While not practically efficient, this accurately reflects the time complexity of the described brute force approach.

Space Complexity

O(N) – The algorithm generates a list of perfect squares less than or equal to N, where N is the input number. In the worst case, if N is large and many perfect squares are smaller than it, this list can grow proportionally to N. While not every number up to N will be a perfect square, the potential for a list that scales with N exists, dominating the auxiliary space. Thus, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The goal is to find the smallest number of perfect squares that add up to a given number. Instead of trying every possible combination, we use a method that remembers the best solutions for smaller numbers to build up to the solution for the bigger number.

Here's how the algorithm would work step-by-step:

Create a chart where each spot represents a number from 0 up to the number you're given.
The first spot (representing 0) is already solved: it takes 0 perfect squares to reach 0.
Now, go through the chart, one number at a time, starting with 1.
For each number, look at all the perfect squares that are less than or equal to that number (like 1, 4, 9, if you are looking at 12).
Subtract each of those perfect squares from your current number and look up the answer in your chart for that smaller number.
Add 1 to that answer (because you used one perfect square to get there). This is the potential solution using that perfect square.
Do this for all the perfect squares, and pick the smallest number of perfect squares you found. Put that answer in your chart.
Continue this process until you reach the number you're trying to solve. The answer in your chart is the smallest number of perfect squares you need.

Code Implementation

def perfect_squares(number):
    number_of_squares = [0] * (number + 1)

    for current_number in range(1, number + 1):
        min_squares_needed = current_number

        # Iterate through all perfect squares <= current number
        square_root = 1
        while square_root * square_root <= current_number:
            square = square_root * square_root

            # Find number of squares needed using a perfect square
            remaining_number = current_number - square
            squares_needed = number_of_squares[remaining_number] + 1

            # Update minimum if a better solution is found
            min_squares_needed = min(min_squares_needed, squares_needed)
            square_root += 1

        # Store the minimum number of perfect squares
        number_of_squares[current_number] = min_squares_needed

    #The last element of the list contains the result
    return number_of_squares[number]

Big(O) Analysis

Time Complexity

O(n*sqrt(n)) – We iterate through each number from 1 to n. For each number i, we iterate through perfect squares less than or equal to i. The number of perfect squares less than or equal to i is bounded by the square root of i, which is at most sqrt(n). Therefore, for each of the n numbers, we perform approximately sqrt(n) operations. This results in a total time complexity of O(n*sqrt(n)).

Space Complexity

O(n) – The algorithm uses a chart (which can be implemented as an array) to store the minimum number of perfect squares needed for each number from 0 up to the input number n. This chart acts as a memoization table, storing intermediate results to avoid redundant calculations. Therefore, the auxiliary space required is proportional to the size of the input number n. This results in an auxiliary space complexity of O(n).

Edge Cases

Case	How to Handle
Input n is 0	Return 0 because no perfect squares are needed to sum to 0.
Input n is 1	Return 1 since 1 is a perfect square itself.
Input n is a perfect square (e.g., 4, 9, 16)	Return 1 immediately because n itself forms a perfect square that sums to n
Large value of n that could cause integer overflow issues during intermediate calculations (specifically when constructing the list of perfect squares or during BFS)	Use long data type for intermediate calculations or apply appropriate bounds checking to prevent integer overflow.
Input n requiring many perfect squares to sum to it (worst-case scenario for performance)	Consider the time complexity of the chosen algorithm and optimize for large n, such as using dynamic programming or a BFS-based approach with pruning.
Input n where the optimal solution involves many small perfect squares (e.g., n=7)	The solution should explore all possible combinations including multiple instances of smaller perfect squares like 1.
Negative Input	Throw an IllegalArgumentException or return -1 as the problem statement specified positive integers only.
Legendre's three-square theorem states that a natural number n can be represented as the sum of three squares of integers if and only if n is not of the form n = 4^a(8b + 7) for nonnegative integers a and b; numbers of this form would require 4 squares.	Applying Legendre's Three Square Theorem can potentially provide a faster solution by reducing the search space when a 4 square solution is required.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer `n`? This will help me consider potential memory usage and algorithm efficiency.
Is `n` guaranteed to be a positive integer, or do I need to handle cases where `n` is zero or negative?
If `n` cannot be represented as a sum of perfect squares, what should the return value be? Is there an error code or a specific default value I should return?
Are we looking for *any* combination of perfect squares that sums to `n`, or should I prioritize using a smaller number of *distinct* perfect squares if multiple solutions with the same count exist?
Can you provide a few example inputs and expected outputs to further clarify the problem and expected behavior?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by listing all perfect squares smaller than or equal to the number you are trying to reach.
Try using just one of those perfect squares to see if it equals your number. If so, you're done!
If not, try all possible pairs of perfect squares from your list and see if any of the pairs add up to your number. If you find one, great!
If no pair works, move on to trying all possible combinations of three perfect squares, and so on.
Continue adding more perfect squares in your combinations until you find a combination that adds up to your number.
As you find valid combinations, keep track of how many perfect squares each combination uses.
Finally, pick the combination that uses the fewest perfect squares; that's your answer!

Code Implementation

def perfect_squares_brute_force(number):
    # Generate perfect squares less than or equal to the input number
    perfect_squares = [square**2 for square in range(1, int(number**0.5) + 1)]

    if number in perfect_squares:
        return 1

    # Iterate through possible number of perfect squares
    for num_squares in range(2, number + 1): 
        # Try combinations of perfect squares
        combinations = find_combinations(number, num_squares, perfect_squares)
        if combinations:
            return num_squares

    return number

def find_combinations(target_number, num_squares, perfect_squares):
    if num_squares == 0:
        return target_number == 0
    if target_number < 0:
        return False

    # Check all possible combinations with recursion
    for perfect_square in perfect_squares:
        if find_combinations(target_number - perfect_square, num_squares - 1, perfect_squares):
            return True

    return False

def num_squares(number):
    # Handle edge case for non-positive numbers
    if number <= 0:
        return 0

    # Use brute force method to find fewest perfect squares
    return perfect_squares_brute_force(number)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a chart where each spot represents a number from 0 up to the number you're given.
The first spot (representing 0) is already solved: it takes 0 perfect squares to reach 0.
Now, go through the chart, one number at a time, starting with 1.
For each number, look at all the perfect squares that are less than or equal to that number (like 1, 4, 9, if you are looking at 12).
Subtract each of those perfect squares from your current number and look up the answer in your chart for that smaller number.
Add 1 to that answer (because you used one perfect square to get there). This is the potential solution using that perfect square.
Do this for all the perfect squares, and pick the smallest number of perfect squares you found. Put that answer in your chart.
Continue this process until you reach the number you're trying to solve. The answer in your chart is the smallest number of perfect squares you need.

Code Implementation

def perfect_squares(number):
    number_of_squares = [0] * (number + 1)

    for current_number in range(1, number + 1):
        min_squares_needed = current_number

        # Iterate through all perfect squares <= current number
        square_root = 1
        while square_root * square_root <= current_number:
            square = square_root * square_root

            # Find number of squares needed using a perfect square
            remaining_number = current_number - square
            squares_needed = number_of_squares[remaining_number] + 1

            # Update minimum if a better solution is found
            min_squares_needed = min(min_squares_needed, squares_needed)
            square_root += 1

        # Store the minimum number of perfect squares
        number_of_squares[current_number] = min_squares_needed

    #The last element of the list contains the result
    return number_of_squares[number]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return 0 because no perfect squares are needed to sum to 0.
Input n is 1	Return 1 since 1 is a perfect square itself.
Input n is a perfect square (e.g., 4, 9, 16)	Return 1 immediately because n itself forms a perfect square that sums to n
Large value of n that could cause integer overflow issues during intermediate calculations (specifically when constructing the list of perfect squares or during BFS)	Use long data type for intermediate calculations or apply appropriate bounds checking to prevent integer overflow.
Input n requiring many perfect squares to sum to it (worst-case scenario for performance)	Consider the time complexity of the chosen algorithm and optimize for large n, such as using dynamic programming or a BFS-based approach with pruning.
Input n where the optimal solution involves many small perfect squares (e.g., n=7)	The solution should explore all possible combinations including multiple instances of smaller perfect squares like 1.
Negative Input	Throw an IllegalArgumentException or return -1 as the problem statement specified positive integers only.
Legendre's three-square theorem states that a natural number n can be represented as the sum of three squares of integers if and only if n is not of the form n = 4^a(8b + 7) for nonnegative integers a and b; numbers of this form would require 4 squares.	Applying Legendre's Three Square Theorem can potentially provide a faster solution by reducing the search space when a 4 square solution is required.