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

Let f(n) be the minimum number of operations to reduce the non-negative integer n to zero. Then, obviously we have:

where i is non-negative integer i.e. where x is a power of two.

We can of course, brute force, for any given n, we can try add or subtract any power of two. However, this is not practically feasible as the time complexity will be exponential.

Let’s consider this, let a and b be the closest two power of two, and c and d are also power of two. i.e. c < a < n < b < d where n is not power of two.

We don’t need to consider any other power of two, since the distance between any two power of two will be power of two. For example, a – c is power of two, and so is d – b, so we just have to consider the closest power of twos: a and b. This should give the optimal.

We can find the largest power of two less than n which is represented as (where i is non-negative integer), and the cost to reduce n to a is , similarly, we can compute the cost to move n to its next power of two, which is .

Then, we just have to choose the smaller cost of these two paths. And from there, there is one more operation to reduce it to zero. We also need to cache the value of f(n) so that it becomes top down dynamic programming algorithm (via memoziation technique).

We can check if a given integer is power of two by checking its binary form (which should contain only 1 bit set).

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minOperations(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if (n & (n - 1)) == 0:
                return 1
            a = int(log2(n))
            b = a + 1
            return min(f(n - (1 << a)), f((1 << b) - n)) + 1

class Solution:
    def minOperations(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if (n & (n - 1)) == 0:
                return 1
            a = int(log2(n))
            b = a + 1
            return min(f(n - (1 << a)), f((1 << b) - n)) + 1

The time complexity is O(LogN) as we are reducing N to LogN every recursive call, and we are caching f(n) values.

Actually, we can perform greedy strategy here, by only choosing the smaller distance, namely, f(min(n – (1 << a), (1 << b) – n)). We want to reduce N as quickly as possible, and even it turns negative, which does not matter as we can add power of two to make it zero.

The order of adding or subtracting does not matter.

To see a rigor math proof on this, stay tuned.

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

class Solution:
    def minOperations(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if (n & (n - 1)) == 0:
                return 1
            a = int(log2(n))
            b = a + 1
            n = min(n - (1 << a), (1 << b) - n)
            return f(n) + 1

class Solution:
    def minOperations(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 0
            if (n & (n - 1)) == 0:
                return 1
            a = int(log2(n))
            b = a + 1
            n = min(n - (1 << a), (1 << b) - n)
            return f(n) + 1

This reduces the number of calls, and the time/space complexity are also O(LogN).

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