Minimum Operations to Reduce an Integer to 0 solution and explanation
Google
9 more videos on this problem
Minimum Operations to Reduce an Integer to 0 || Leetcode-2571 || C++Aryan Mittal · 18:12 · 5K views
2571. Minimum Operations to Reduce an Integer to 0 | LeetCode Medium | Weekly 333Deep Tech · 9:50 · 3K views
LeetCode Weekly Contest 333 | 2571: Minimum Operations to Reduce an Integer to 0 SolutionCoding Community | Newton School · 11:43 · 3K views
6365. Minimum Operations to Reduce an Integer to 0 | LeetCode Weekly 333 | C++Priyanshi Porwal · 5:53 · 1K views
Leetcode Weekly contest 333 - Medium - Minimum Operations to Reduce an Integer to 0Prakhar Agrawal · 9:20 · 1K views
Minimum Operations to Reduce an Integer to 0 | Weekly Contest 333 | LeetcodecodingMohan · 9:01 · 1K views
2571. Minimum Operations to Reduce an Integer to 0 (Leetcode Medium)Programming Live with Larry · 18:51 · 1K views
Minimum Operations to Reduce an Integer to 0 | Leetcode 2571 | Weekly Contest 333Algorithms Casts · 11:32 · 822 views
B. Minimum Operations to Reduce an Integer to 0 - LEETCODE WEEKLY CONTEST 333 (Code + Explanation)Joyjit Codes · 4:39 · 820 views
【每日一题】LeetCode 2571. Minimum Operations to Reduce an Integer to 0Huifeng Guan · 12:39 · 605 views
The problem
You are given a positive integer n, you can do the following operation any number of times:
- Add or subtract a power of
2fromn.
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
Approach overview
Problem Overview: You are given an integer n. In one operation you can add or subtract any power of two (2^k). The goal is to reduce the number to exactly 0 using the minimum number of operations.
Approach 1: Binary Representation Manipulation (O(log n) time, O(1) space)
This approach works directly on the binary representation of n. Each power of two corresponds to a single bit, so the task becomes minimizing the number of bit adjustments needed to turn the number into zero. Iterate through the bits from least significant to most significant. When you encounter consecutive 1s, it is often better to perform a carry by adding a power of two rather than subtracting repeatedly. This turns a block like 111 into 1000, reducing future operations. The algorithm essentially simulates how binary addition and subtraction propagate carries while scanning the bits. Because the number of bits in n is O(log n), the entire process runs in logarithmic time. This technique relies heavily on understanding bit manipulation patterns and how binary carries affect optimal decisions.
Approach 2: Greedy Power of Two Matching (O(log n) time, O(1) space)
The greedy strategy focuses on choosing the power of two that moves n closest to zero at each step. Compute the lowest set bit using n & -n. That value represents the smallest power of two currently contributing to the number. The key decision is whether subtracting that value or adding the next power of two leads to fewer remaining set bits. If subtracting creates a long chain of borrows (many adjacent 1s), adding the next power of two collapses the sequence via a carry. This greedy decision works because powers of two form a canonical representation of integers, making local improvements globally optimal. The method repeatedly updates n until it becomes zero, performing at most one operation per bit. The logic naturally connects with concepts from greedy algorithms and bit counting.
Recommended for interviews: The greedy bit-based solution is what most interviewers expect. It shows you understand binary structure and can reason about carries in bit operations. A brute-force or dynamic programming idea demonstrates correctness thinking, but the greedy bit manipulation solution proves you can optimize using properties of powers of two.
Approach 1: Binary Representation Manipulation
This approach leverages the binary representation of the integer. Each bit in the binary form of the number denotes whether a particular power of 2 is present or not. Flipping each bit can effectively add or subtract the power of 2 it represents. We can make use of bitwise operations to achieve this and count the number of necessary operations.
def minOperations(n):
operations = 0
while n > 0:
operations += n & 1
n >>= 1
return operations
n = 54
print(minOperations(n))public class MinOperations {
public static int minOperations(int n) {
int operations = 0;
while (n > 0) {
operations += n & 1;
n >>= 1;
}
return operations;
}
public static void main(String[] args) {
int n = 39;
System.out.println(minOperations(n));
}
}#include <iostream>
int minOperations(int n) {
int operations = 0;
while (n > 0) {
operations += n & 1;
n >>= 1;
}
return operations;
}
int main() {
int n = 54;
std::cout << minOperations(n);
return 0;
}function minOperations(n) {
let operations = 0;
while (n > 0) {
operations += n & 1;
n >>>= 1;
}
return operations;
}
const n = 39;
console.log(minOperations(n));#include <stdio.h>
int minOperations(int n) {
int operations = 0;
while (n > 0) {
if (n & 1) {
operations++;
n ^= 1;
}
n >>= 1;
}
return operations;
}
int main() {
int n = 39;
printf("%d", minOperations(n));
return 0;
}using System;
class MinOperations {
static int MinOperationsToZero(int n) {
int operations = 0;
while (n > 0) {
operations += n & 1;
n >>= 1;
}
return operations;
}
static void Main() {
int n = 54;
Console.WriteLine(MinOperationsToZero(n));
}
}The Python version leverages the same bit manipulation tactic, incrementing the count based on the result of n & 1 and shifting n to its right. Here, operations accumulates the minimum toggles needed for reaching 0.
The time complexity is O(b) due to iterating over the bits of n. As for space, it's minimal, at O(1).
Approach 2: Greedy Power of Two Matching
This method prioritizes matching and subtracting/add operations for powers of 2 greedily. The target's binary form aids in deciding which power to manipulate. The approach effectively maps adjacent '1' combinations—adding to higher powers and removing lesser ones.
import math
def min_operations(n):
if n == 0:
return 0
nearest = 2 ** math.floor(math.log2(n))
return 1 + min(min_operations(abs(n - nearest)), min_operations(abs(n - nearest * 2)))
n = 54
print(min_operations(n))public class MinOperationsGreedy {
public static int minOperations(int n) {
if (n == 0) return 0;
int nearest = (int) Math.pow(2, Math.floor(Math.log(n) / Math.log(2)));
int val1 = Math.abs(n - nearest);
int val2 = Math.abs(n - 2 * nearest);
return 1 + (val1 < val2 ? minOperations(val1) : minOperations(val2));
}
public static void main(String[] args) {
int n = 39;
System.out.println(minOperations(n));
}
}#include <iostream>
#include <cmath>
int minOperations(int n) {
if (n == 0) return 0;
int nearest = pow(2, floor(log2(n)));
int val1 = std::abs(n - nearest);
int val2 = std::abs(n - nearest * 2);
return 1 + (val1 < val2 ? minOperations(val1) : minOperations(val2));
}
int main() {
int n = 54;
std::cout << minOperations(n);
return 0;
}function minOperations(n) {
if (n === 0) return 0;
const nearest = Math.pow(2, Math.floor(Math.log2(n)));
const val1 = Math.abs(n - nearest);
const val2 = Math.abs(n - 2 * nearest);
return 1 + Math.min(minOperations(val1), minOperations(val2));
}
const n = 54;
console.log(minOperations(n));#include <stdio.h>
#include <math.h>
int minOperations(int n) {
if (n == 0) return 0;
int nearest = pow(2, floor(log2(n)));
int val1 = abs(n - nearest);
int val2 = abs(n - nearest * 2);
return 1 + (val1 < val2 ? minOperations(val1) : minOperations(val2));
}
int main() {
int n = 39;
printf("%d", minOperations(n));
return 0;
}using System;
class MinOperationsGreedy {
static int MinOperations(int n) {
if (n == 0) return 0;
int nearest = (int)Math.Pow(2, Math.Floor(Math.Log(n) / Math.Log(2)));
int val1 = Math.Abs(n - nearest);
int val2 = Math.Abs(n - 2 * nearest);
return 1 + (val1 < val2 ? MinOperations(val1) : MinOperations(val2));
}
static void Main() {
int n = 39;
Console.WriteLine(MinOperations(n));
}
}In Python, nearest power selection uses log2. Deciding recursive path branches via min ensures extracting lesser operations while zeroing in on n effectively.
Time complexity approximates O(log(n)), alongside a stack-intensive space estimated to be O(log(n)).
Approach 3: Greedy + Bitwise Operation
We convert the integer n to binary, starting from the lowest bit:
- If the current bit is 1, we accumulate the current number of consecutive 1s;
- If the current bit is 0, we check whether the current number of consecutive 1s is greater than 0. If it is, we check whether the current number of consecutive 1s is 1. If it is, it means that we can eliminate 1 through one operation; if it is greater than 1, it means that we can reduce the number of consecutive 1s to 1 through one operation.
Finally, we also need to check whether the current number of consecutive 1s is 1. If it is, it means that we can eliminate 1 through one operation; if it is greater than 1, we can eliminate the consecutive 1s through two operations.
The time complexity is O(log n), and the space complexity is O(1). Here, n is the given integer in the problem.
function minOperations(n: number): number {
let [ans, cnt] = [0, 0];
for (; n; n >>= 1) {
if (n & 1) {
++cnt;
} else if (cnt) {
++ans;
cnt = cnt === 1 ? 0 : 1;
}
}
if (cnt === 1) {
++ans;
} else if (cnt > 1) {
ans += 2;
}
return ans;
}func minOperations(n int) (ans int) {
cnt := 0
for ; n > 0; n >>= 1 {
if n&1 == 1 {
cnt++
} else if cnt > 0 {
ans++
if cnt == 1 {
cnt = 0
} else {
cnt = 1
}
}
}
if cnt == 1 {
ans++
} else if cnt > 1 {
ans += 2
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Representation Manipulation | The time complexity is |
| Greedy Power of Two Matching | Time complexity approximates |
| Greedy + Bitwise Operation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Representation Manipulation | O(log n) | O(1) | Best general solution when working directly with bit patterns and minimizing operations via carry handling |
| Greedy Power of Two Matching | O(log n) | O(1) | Preferred in interviews when explaining decisions using lowest set bit and greedy updates |
| Dynamic Programming (conceptual) | O(n log n) | O(n) | Useful for understanding the problem as a state transition problem but impractical for large n |
Frequently asked questions
Is Minimum Operations to Reduce an Integer to 0 easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 60%. The challenge is recognizing that binary carry behavior determines the optimal choice between adding and subtracting powers of two. Once that insight is clear, the implementation becomes straightforward.
Minimum Operations to Reduce an Integer to 0 Python/Java solution
The typical Python or Java implementation repeatedly checks the lowest set bit using operations like n & -n. Based on the surrounding bit pattern, the algorithm either adds or subtracts that power of two. The loop continues until n becomes zero, giving an O(log n) time and O(1) space implementation.
How to solve Minimum Operations to Reduce an Integer to 0 in O(log n)?
Convert the integer into its binary form and process the bits from least significant to most significant. When a block of consecutive 1s appears, adding a power of two can create a carry that eliminates multiple bits at once. Otherwise subtract the lowest set bit. This greedy strategy guarantees the minimum operations in logarithmic time.
What is the best approach for Minimum Operations to Reduce an Integer to 0?
The most efficient approach uses greedy bit manipulation. By examining the binary representation of n, you decide whether adding or subtracting a power of two reduces the number of set bits most effectively. Handling sequences of consecutive 1s with a carry operation often reduces multiple operations into one. This solution runs in O(log n) time and O(1) space.
Is Minimum Operations to Reduce an Integer to 0 asked at Google/Amazon/Meta?
Bit manipulation and greedy optimization problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of binary representations, bitwise operations, and reasoning about optimal decisions.
What data structure is used in Minimum Operations to Reduce an Integer to 0?
No complex data structure is required. The solution relies on bitwise operations and integer arithmetic while analyzing the binary representation of the number. Concepts from greedy algorithms and bit manipulation are the primary tools.
What is the time complexity of Minimum Operations to Reduce an Integer to 0?
The optimal solution runs in O(log n) time because the algorithm processes the binary representation of the number. Each operation examines or modifies bits, and an integer contains at most log2(n) bits. Space complexity is O(1) since the computation only tracks a few variables.