Solving Perfect Squares problem using breadth-first search
By Dmitry Kabanov
I was learning recently about solving problems that use breadth-first search (BFS). This is a family of computer science algorithms that traverse tree data structures “by levels”. That is, starting at the root, we process all nodes on level 1, then all nodes on level 2, etc.
One typical application of BFS is to find the shortest path between the root and the given nodes.
To implement BFS, one should use the queue data structure.
The schema of the algorithm is the following (in pseudocode mixture of C and Python):
Given: root node, target node
add the root node to the queue
level = 0
while queue is not empty:
# iterate over the nodes that are on the same level.
size = queue.size()
for (i = 0; i < size; i++):
curr = pop the first node from the queue
if curr is the target node, then return level
add all neighbors of curr to the queue
level++
return -1
Note that we return value of the level
variable, when the currently
processed node is the given target.
If this condition is not met during the tree traversal, we return -1.
An example of the problem that can be solved using BFS is the Perfect Squares problem.
The statement of the problem is to find the minimal number of perfect squares
that sum up to the given number n
.
The perfect square is an integer that is a square of another integer,
for example, \(9 = 3^2\), therefore, 9 is the perfect square.
So, if n
is 13, the answer is 2 as \(13 = 9 + 4\).
The solution in Python using BFS is the following.
import math
from collections import deque
def min_num_of_squares(n: int) -> int:
squares = []
i = 1
while i**2 <= n:
squares.append(i**2)
i += 1
# Initialize the queue with root node `0`.
queue = deque([0])
# We need at least one summand in the sum of squares to get `n`.
step = 1
while queue:
# Process elements of the queue from the same level.
# Note that, although `len(queue)` is dynamic,
# when we initialize `range`, it is fixed, that is,
# `range` will not be affected by the changes
# of the queue length while processing nodes
# of the same level.
for __ in range(len(queue)):
curr = queue.popleft()
# Process potential squares of the `curr` node.
for sq in squares:
if curr + sq == n:
return step
if curr + sq > n:
break
if curr + sq < n:
queue.append(curr + sq)
step += 1
return -1
Breadth-first search approach to this problem visually can be thought of
as the root node “zero” at the center,
surrounded by “circles” of perfect squares.
And the solution is the minimal number of such “circles”
that we need to draw, such that there is a sum of numbers that gives n
.
In practice, the “circles” are incomplete
as we do not have to process elements
that lead the sum to exceed the given number n
.