Perfect Squares LeetCode

Key takeaways
A perfect square is a number that can be expressed as the product of an integer with itself, like $1 (1*1)$ , $4 (2*2)$ , or $16 (4*4)$ .
Perfect Squares LeetCode problem statement is given an integer n, determine the minimum number of perfect square numbers that add up to n.
Breadth-first search (BFS) is used to determine the minimum number of perfect square numbers that add up to n.
The time complexity is approximately is $O\left(n^{\frac{h}{2}}\right)$ .
The space complexity is also $O\left(n^{\frac{h}{2}}\right)$ .

Imagine you have a number that can be expressed as the product of an integer with itself. These numbers are known as perfect squares. For example, if you take the number $1$ , it can be written as $1*1$ . Similarly, $4$ can be written as $2*2$ , $9$ as $3*3$ , and $16$ as $4*4$ . These numbers, called perfect squares, have many applications in various branches of mathematics.

Problem statement

Given an integer n, determine the minimum number of perfect square numbers that add up to n. For example, perfect squares such as $1$ , $4$ , $9$ , and $16$ can be used in the sum, but numbers like $5$ and $10$ cannot. Your task is to find the smallest count of these perfect square numbers needed to sum exactly to the given integer n.

Constraints:

$1 \leq$ n $\leq 10^4$

Example

Solution

In this solution, finding the minimum number of perfect square numbers is visualized as a shortest path problem in an unweighted graph where each node represents a remainder of $n$ after subtracting some perfect squares, and each edge represents the subtraction of a perfect square. Using breadth-first search (BFS), we can explore the shortest path from $n$ to $0$ , corresponding to the minimum number of perfect squares that sum to $n$ .

Let’s look at how the implementation of the algorithm works:

Generate perfect squares:
1. The first step is to generate a list of perfect squares that are less than or equal to n. These perfect squares will be used to reduce the given number n.
2. We do this by iterating from $1$ up to the integer square root of n (inclusive) and squaring each number.
Initialize BFS variables:
1. Initialize a level counter level to $0$ . This counter keeps track of the number of levels we’ve processed in the BFS, corresponding to the number of perfect squares used so far.
2. Initialize a queue (implemented as a set for efficient membership testing) with the initial value n. This queue will store the remainder as we subtract perfect squares.
BFS loop:
1. Begin the BFS loop, which continues until the queue is empty.
2. Increment the level counter by $1$ to represent moving to the next depth level in the BFS.
3. Initialize an empty set next_queue to hold the remainder for the next level of BFS.
Process current level:
1. Try subtracting each perfect square from each remainder in the current queue.
  1. If the remainder equals a perfect square, return the current level because we’ve found the solution at this level.
  2. If the remainder is less than a perfect square, break out of the inner loop since no further perfect squares can be subtracted meaningfully.
  3. Otherwise, add the new remainder remainder - square_num to the next_queue.
Prepare for the next level:
1. Assign next_queue to queue to process the next level in the subsequent iteration of the while loop.
Return result:
1. The function returns the level, which is the minimum number of perfect squares that sum to n.

Let’s look at the illustration below to better understand the solution:

def perfect_squares_upto_n(n):
    # Generate a list of perfect square numbers up to the square root of n
    squares = [i * i for i in range(1, int(n**0.5) + 1)]
    level = 0
    queue = {(n, ())}
    # Iterate over each remainder in the current queue
    while queue:
        level += 1
        updated_queue = set()
        
        for remainder, path in queue:
            for square in squares:
                # If the remainder equals the current perfect square number,
                # return the current level as the minimum number of perfect squares
                if remainder == square:
                    path += (square,)
                    return level, path
                # If the remainder is less than the current perfect square number,
                # break the loop because further perfect square numbers will be larger
                elif remainder < square:
                    break
                # If the remainder is greater than the current perfect square number,
                # add the difference to the updatedQueue for further processing
                else:
                    updated_queue.add((remainder - square, path + (square,)))    
        queue = updated_queue
    
    return level, []
# Driver code
def main():
    n = [13, 344, 561, 78, 900]
    
    for number in n:
        squares_count, squares_used = perfect_squares_upto_n(number)
        print("n = ", number)
        print("Minimum squares = ", squares_count)
        print("Perfect squares used = ", squares_used)
        print("-" * 100)
if __name__ == "__main__":
    main()

Perfect Squares

Let’s look at the time and space complexity of this solution:

Time complexity

The time complexity of this solution is $O(\frac{\sqrt{n^{h+1}-1}}{\sqrt{n-1}}) = O(n^\frac{h}{2})$ where $h$ is the height of the N-ary tree and $\frac{{n^{h+1}-1}}{{n-1}}$ is the formula to calculate the number of nodes in a complete N-ary tree. Let’s look at the breakdown of the time complexity:

For a complete N-ary tree of height $h$ and where each node has $n$ children, the total number of nodes in the tree can be calculated using the formula: $\text{nodes} = \frac{n^{h+1} - 1}{n - 1}$ . This formula comes from summing the geometric series: $1 + n + n^2 + \dots + n^h = \frac{n^{h+1} - 1}{n - 1}$
When we traverse all the nodes, the time complexity is directly proportional to the total number of nodes, which is $\frac{n^{h+1} - 1}{n - 1}$ . For large $n$ , this simplifies to: $O\left(\frac{n^{h+1} - 1}{n - 1}\right) \approx O\left(n^h\right)$
The final time complexity is approximately $O\left(n^{\frac{h}{2}}\right)$ , indicating that the time complexity grows exponentially with the tree’s height.

Space complexity

The space complexity is $O(n^\frac{h}{2})$ , which represents the maximum number of nodes that can appear at level $h$ . While we maintain a list of perfect squares square_nums, the primary space usage comes from the queue variable. This variable tracks the remainders that must be visited for a given level in the N-ary tree. In the worst case, the number of nodes at the level $h$ can be as large as $n$ raised to the power of $\frac{h}{2}$ . This is because:

Each level potentially multiplies the number of nodes by a factor related to the number of perfect squares that can be subtracted.
Since perfect squares are a sequence like $1, 4, 9, 16, ...,$ the number of new nodes generated by a single node at level $h$ is bounded by ${\sqrt{n}}$ .
If we raise ${\sqrt{n}}$ to the power of $h$ , we get $n^\frac{h}{2}$ .

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How do you code a perfect square in Python?

While you can’t directly code a perfect square as a data type in Python, you can create functions or classes to represent and manipulate perfect squares. Here is an example code:

def perfect_squares_upto_n(n):
    # Generate a list of perfect square numbers up to the square root of n
    squares = [i * i for i in range(1, int(n**0.5) + 1)]
    level = 0
    queue = {(n, ())}

    # Iterate over each remainder in the current queue
    while queue:
        level += 1
        updated_queue = set()
        
        for remainder, path in queue:
            for square in squares:
                # If the remainder equals the current perfect square number,
                # return the current level as the minimum number of perfect squares
                if remainder == square:
                    path += (square,)
                    return level, path
                # If the remainder is less than the current perfect square number,
                # break the loop because further perfect square numbers will be larger
                elif remainder < square:
                    break
                # If the remainder is greater than the current perfect square number,
                # add the difference to the updatedQueue for further processing
                else:
                    updated_queue.add((remainder - square, path + (square,)))    
        queue = updated_queue
    
    return level, []

# Driver code
def main():
    n = [13, 344, 561, 78, 900]
    
    for number in n:
        squares_count, squares_used = perfect_squares_upto_n(number)
        print("n = ", number)
        print("Minimum squares = ", squares_count)
        print("Perfect squares used = ", squares_used)
        print("-" * 100)

if __name__ == "__main__":
    main()

What is the logic of a perfect square?

A perfect square is a number that is the product of another integer multiplied by itself. In other words, it’s the square of an integer. For example, 4 is a perfect square because it’s the square of $2 (2 * 2 = 4)$ .

Is 0 a perfect square?

Yes, 0 is a perfect square. It’s the square of $0 (0 * 0 = 0)$ .

Free Resources