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

ACMer

3 years ago

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

–EOF (The Ultimate Computing & Technology Blog) —

1806 words
Last Post: Teaching Kids Programming - Minimum Operations to Reduce an Integer to 0 (Greedy/Iterative Algorithm)
Next Post: Starting a Business with Telegram Bots: Creative Ideas to Inspire You

The Permanent URL is: Teaching Kids Programming – Minimum Operations to Reduce an Integer to 0 (Recursion with Math Proof) (AMP Version)

Minimum Operations to Reduce an Integer to 0 (Math Analysis + Another Recursion)

f(n) when n is even number

f(n) when n is odd number

Minimum Operations to Reduce an Integer to 0

Related posts: