algoadvance

Leetcode 2220. Minimum Bit Flips to Convert Number

Problem Statement

You are given two integers start and goal. The task is to determine the minimum number of bit flips required to convert start to goal.

Constraints

• 0 <= start, goal <= 10^9

Clarifying Questions

1. Can start and goal be the same?
   • Yes, in that case, the number of bit flips required would be 0.
2. What is the format of the input and the expected output?
   • Both inputs are integers. The output is an integer representing the minimum number of bit flips.

Strategy

1. XOR Operation:
   • start XOR goal will give a number where each bit is 1 if the corresponding bits of start and goal differ.
2. Counting Set Bits:
   • The problem then reduces to counting the number of 1’s in the result of the XOR operation, as each 1 represents a bit that needs to be flipped.

Code

public class MinimumBitFlips {
    public static int minBitFlips(int start, int goal) {
        // XOR operation to find differing bits
        int xorResult = start ^ goal;
        
        // Count the number of 1's in the XOR result
        int count = 0;
        while (xorResult != 0) {
            count += xorResult & 1;
            xorResult >>= 1;
        }
        
        return count;
    }

    public static void main(String[] args) {
        // Sample run
        int start = 10; // Binary: 1010
        int goal = 20; // Binary: 10100
        System.out.println(minBitFlips(start, goal)); // Output should be 4 (since 1010 -> 10100)
    }
}

Time Complexity

• The time complexity is O(1) because the number of bits in a 32-bit integer (representing the integer bounds of 10^9) is constant and small. The operations we are performing (XOR and bit counting) are linear relative to this fixed number of bits. This means that the complexity can be considered constant with respect to the input size.

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?