Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 using Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a positive integer n, you can do the following operation any number of times:

• Add or subtract a power of 2 from n.
• Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2i where i >= 0.

Example 1:
Input: n = 39
Output: 3
Explanation: We can do the following operations:
– Add 20 = 1 to n, so now n = 40.
– Subtract 23 = 8 from n, so now n = 32.
– Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

Example 2:
Input: n = 54
Output: 3
Explanation: We can do the following operations:
– Add 21 = 2 to n, so now n = 56.
– Add 23 = 8 to n, so now n = 64.
– Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

Constraints:
1 <= n <= 10^5

Minimum Operations to Reduce an Integer to 0 using Breadth First Search Algorithm

We can search the shortest path in a unweighted graph using Breadth First Search Algorithm. The root of the search tree is the given number (starting point). We also store the distance to the root in each node. When we find the “0”, we know the shortest distance aka the minimum number of operations.

However, the search tree is huge, as the branch factor is 64 (2^0, 2^1, ..2^31) and we have to consider addition and subtraction for each power of two.

Also, we need a hash set to remember the nodes that we have seen.

We can set a boundary (or window), so to ignore those nodes whose values are too large or too small.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def minOperations(self, n: int) -> int:
        seen = set()
        q = deque([(n, 0)])
        power_of_two = [2**i for i in range(32)]
        while q:
            m, d = q.popleft()
            if m == 0:
                return d
            for x in power_of_two:
                for nx in (m - x, m + x):
                    if nx not in seen and abs(nx) <= 10**5:
                        seen.add(nx)
                        q.append((nx, d + 1))    

class Solution:
    def minOperations(self, n: int) -> int:
        seen = set()
        q = deque([(n, 0)])
        power_of_two = [2**i for i in range(32)]
        while q:
            m, d = q.popleft()
            if m == 0:
                return d
            for x in power_of_two:
                for nx in (m - x, m + x):
                    if nx not in seen and abs(nx) <= 10**5:
                        seen.add(nx)
                        q.append((nx, d + 1))    

Minimum Operations to Reduce an Integer to 0

• Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 using Breadth First Search Algorithm
• Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Greedy Based on Binary Bits)
• Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Math Analysis + Another Recursion)
• Teaching Kids Programming - Minimum Operations to Reduce an Integer to 0 (Greedy/Iterative Algorithm)
• Teaching Kids Programming - Minimum Operations to Reduce an Integer to 0 (Greedy Recursion/Top Down Dynamic Programming Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —