Watch 10 video solutions for Minimum Operations to Reduce an Integer to 0, a medium level problem involving Dynamic Programming, Greedy, Bit Manipulation. This walkthrough by NeetCodeIO has 16,975 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer n, you can do the following operation any number of times:
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 <= 105