Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Greedy Based on Binary Bits)

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 Based on Binary Bits)

We can look at the binary form of any given positive integer. If the last two bits are 11, then we can greedily add one to make it 100.. so that requires two steps. Otherwise, we can remove each one separately. The following time complexity is O(LogN). The space complexity is O(1).

For example, 7 in binary is 111, we can add one which makes it 1000 and then remove it which needs 2 steps overall. This is better than removing 3 ones (each one is a power of two) one by one.

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

class Solution:
    def minOperations(self, n: int) -> int:
 
        def f(n):
            if n == 0:
                return 0
            ans = 0
            while n:
                if n & 3 == 3:
                    ans += 1
                    n += 1
                else:                    
                    ans += n & 1
                    n >>= 1
            return ans
 
        return f(n)

class Solution:
    def minOperations(self, n: int) -> int:

        def f(n):
            if n == 0:
                return 0
            ans = 0
            while n:
                if n & 3 == 3:
                    ans += 1
                    n += 1
                else:                    
                    ans += n & 1
                    n >>= 1
            return ans

        return f(n)

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