Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Recursion with Math Proof)

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 (Math Analysis + Another Recursion)

Let be the minimum number of operations to bring down to zero. With every operation, we can add or subtract any power of two . Let’s rewrite it:

where

Then the number of operations equals

f(n) when n is even number

If is even number, i.e.

Then,

If we divide two on both sides

so for any given integer n’ because we have a one-to-one mapping between and so the must be optimal as otherwise we could just optimize it.

f(n) when n is odd number

If is odd number, i.e.

Then, or

if , we can subtract one and divide by two on both sides:
if , we can add one and divide by two on both sides:

So, for we must search in and .

Thus we have a recursive formula for where we can reduce n by half:

when is even and:
when is odd.

We can then implement the above formula using Top Down Dynamic Programming (Recursion with Memoization):

class Solution:
    def minOperations(self, n: int) -> int:
        @cache
        def f(x):
            if x == 0:
                return 0
            if x == 1:
                return 1            
            y = x // 2
            if x & 1:                
                return min(f(y), f(y + 1)) + 1
            return f(y)

        return f(n)

The time/space complexity is O(LogN).

The following are easy to understand/observe:

• The order of operations do not matter, for example, 7=-1+8 or 7=8-1
• We can not have additions of same power of twos, for example: +4+4=+8, the former needs two steps, and the latter needs one step.
• Similarly, we cannot have subtraction off the same power of twos.
• And, also we cannot have addition and subtraction of the same power of twos, since the sum will be zero.

From the definition, we can easily prove that:

For example, to transform x to x+1, we need one step.

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