algoadvance

Leetcode 3226. Number of Bit Changes to Make Two Integers Equal

Problem Statement

Given two integers start and goal, return the number of bit positions in which the two numbers differ. In other words, find how many bits are different between the binary representation of start and goal.

For example:

• If start is 3 (which is 011 in binary) and goal is 5 (which is 101 in binary), the function should return 2 because the bits at positions 0 and 1 are different.

Clarifying Questions

1. What is the range of input values for start and goal?
   • Typically, they are 32-bit integers.
2. Should we handle negative numbers?
   • Yes, negative numbers can be handled using their two’s complement representation.
3. Is the function expected to be performant for any value within the 32-bit range?
   • Yes, the operation should ideally be O(1) since we mainly work on binary representation.

These clarifications confirm the scope and expected handling of the inputs.

Strategy

1. To find the number of differing bits between start and goal, we can employ the XOR operation (^), which yields a bit set to 1 only where the bits of its operands differ.
   • Example: start = 3 (011), goal = 5 (101). The XOR result is 011 ^ 101 = 110.
2. Next, we need to count the number of 1s in the result of start ^ goal. This can be achieved using the __builtin_popcount method in GCC/Clang or manually counting the bits.

Steps:

1. Compute the XOR of start and goal.
2. Count the number of 1s in the binary representation of the XOR result using a bitwise operation loop.

Code

#include <iostream>

int minBitFlips(int start, int goal) {
    // Step 1: XOR start and goal to get differing bits
    int xor_result = start ^ goal;
    
    // Step 2: Count the number of 1 bits in the xor_result
    int count = 0;
    while (xor_result) {
        count += xor_result & 1;
        xor_result >>= 1;
    }
    
    return count;
}

int main() {
    int start = 3;
    int goal = 5;
    std::cout << "Number of bit changes: " << minBitFlips(start, goal) << std::endl;
    return 0;
}

Time Complexity

The time complexity of the proposed solution is:

• O(1): Since we are operating on a fixed number of bits (e.g., 32 for standard integers), the loop to count bits set to 1 will always perform a constant number of operations.

The provided solution adheres to the expected performance considerations for bit manipulation problems involving fixed-width integers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?