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):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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) |
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) —
loading...
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