2749. Minimum Operations to Make the Integer Zero

UnknownView on LeetCode

Array Bit Manipulation

Time: O(log n)

Space: O(1)

Intuition

Check if (num1 XOR num2) can equal num3 for a pair from array. Enumerate or bit manipulation.

Algorithm

1For each pair (i,j): if nums[i] XOR nums[j] exists in nums: return true.
2Optimize: HashSet lookup.

Common Pitfalls

•O(n^2) enumeration with HashSet lookup for third element. Or XOR properties.

2749.cs

// Approach: Try k operations; need k <= popcount(num1 - k*num2) and k >= popcount.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int MakeTheIntegerZero(int num1, int num2)
    {
        if (num1 == 0)
            return 0;

        for (long op = 1; op < 36; op++)
        {
            long req = (long)num1 - op * num2;
            if (countSetBits(req) <= op && op <= req)
                return (int)op;
        }

        return -1;
    }

    int countSetBits(long x)
    {
        int res = 0;
        for (int i = 0; i < 64; i++)
        {
            if (((1L << i) & x) != 0)
                res++;
        }

        return res;
    }
}

Was this solution helpful?