LeetCode 2749. Minimum Operations to Make the Integer Zero. use c++

视频信息

答案文本 复制

视频字幕 复制

Today we'll solve LeetCode problem 2749: Minimum Operations to Make the Integer Zero. In this problem, we're given two integers num1 and num2. In each operation, we can choose an integer i between 0 and 60, then subtract 2 to the power of i plus num2 from num1. Our goal is to find the minimum number of operations needed to make num1 equal to zero, or return negative one if it's impossible. Let's look at the examples to understand better. Now let's analyze the key mathematical insights behind this problem. Each operation subtracts 2 to the power of i plus num2 from num1. We can rearrange this as: num1 minus k times num2 equals the sum of k powers of 2, where k is the number of operations. This gives us three important conditions: first, num1 minus k times num2 must be positive. Second, this value must have at least k set bits in its binary representation. Third, the value cannot exceed the sum of the k largest possible powers of 2. The minimum operations is the smallest k satisfying these constraints. Now let's develop our algorithm based on the insights. We iterate through possible values of k from 1 to 50. For each k, we calculate the target value as num1 minus k times num2. If the target is positive, we check two conditions: k must be less than or equal to the population count of target, and k must be less than or equal to target itself. Let's trace through the example where num1 equals 3 and num2 equals negative 2. For k equals 1, target is 5, which has 2 set bits. Since 1 is between 2 and 5, this is valid. We continue until we find k equals 3 gives us the answer. Let's walk through several examples to solidify our understanding. For the first test case with num1 equals 3 and num2 equals negative 2, we try different values of k. When k equals 1, target is 5 with 2 set bits, satisfying our conditions. When k equals 2, target is 7 with 3 set bits, also valid. But when k equals 3, target is 9 with only 2 set bits, which fails our condition since we need at least 3 set bits. So the answer is 3. For the second case with num1 equals 5 and num2 equals 7, all k values produce negative targets, making it impossible, so we return negative 1.