2220. Minimum Bit Flips to Convert Number

EasyView on LeetCode

Bit Manipulation

Time: O(1)

Space: O(1)

Problem Overview

Flipping bits where start and goal differ is exactly the number of 1-bits in start XOR goal.

Intuition

Flipping bits where start and goal differ is exactly the number of 1-bits in start XOR goal. Each differing bit needs one flip; matching bits need zero.

Algorithm

1Compute xor = start ^ goal.
2Return population count (Hamming weight) of xor.
3In C#: BitOperations.PopCount((uint)xor) or loop with xor &= xor-1.

Example Walkthrough

Input: start = 3 (011), goal = 4 (100)

1.3 ^ 4 = 7 (111) — three bits differ.

Output: 3

Common Pitfalls

•XOR marks differing bits; do not flip bit-by-bit in a loop unless asked.
•Works for non-negative integers in problem constraints.
•O(1) bit operations vs O(log n) per-bit loop.

2220.cs

// Approach: XOR start and goal; count set bits (number of differing bit positions).
// Time: O(1) Space: O(1)

public class Solution
{
    public int MinBitFlips(int start, int goal)
    {
        int flip = 0;
        for (int i = 0; i < 32; i++)
        {
            int sBit = (start >> i) & 1;
            int gBit = (goal >> i) & 1;
            if (sBit != gBit)
                flip++;
        }

        return flip;
    }
}

Was this solution helpful?