Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Greedy/Iterative 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 (Greedy/Iterative Algorithm)

This post will translate the Recursion of the Greedy Algorithm in the last talk into Iterative Version.

Basically, we choose the closest power of two as a greedy strategy trying to reduce the integer N to zero as quickly as possible.

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

class Solution:
    def minOperations(self, n: int) -> int:
        ans = 0
        while n > 0:
            ans += 1
            ## the following check is optional
            ## if it is power of two, break the loop
            if (n & (n - 1)) == 0:
                break
            a = int(log2(n))
            b = a + 1
            n = min(n - (1 << a), (1 << b) - n)
        return ans

class Solution:
    def minOperations(self, n: int) -> int:
        ans = 0
        while n > 0:
            ans += 1
            ## the following check is optional
            ## if it is power of two, break the loop
            if (n & (n - 1)) == 0:
                break
            a = int(log2(n))
            b = a + 1
            n = min(n - (1 << a), (1 << b) - n)
        return ans

The time complexity is O(LogN) – and the space complexity is O(1) constant.

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) —