💬 Discord
Sign In
NeetCode #856LC-2220EasyBit Manipulation
← Back to All Problems

#856 · #2220 · Minimum Bit Flips to Convert Number(转换数字的最少位翻转次数)

📌 Problem Statement & Constraints

Given two integers start and goal, return the minimum number of bit flips required to turn start into goal. Constraints: 0 <= start, goal <= 10^9.

💡 Core Algorithmic Approaches

  1. A bit flip changes exactly one bit, so only the positions where the two numbers differ need work.
  2. start ^ goal has a 1 in precisely those differing positions.
  3. The minimum number of flips is therefore the popcount of that XOR.
  4. No strategy can do better, because each flip fixes exactly one differing bit.

💻 Benchmark Python3 Implementation

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        return bin(start ^ goal).count("1")   # one flip per differing bit

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(32) = O(1): a constant number of bit positions.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Comparing the numbers arithmetically: the difference in value is unrelated to the number of bit flips.
  • Forgetting that XOR marks the differences: start ^ goal is exactly the mask of bits to flip.
  • Using a hand-written loop when the built-in is available: both are fine, but the XOR is the key insight.
  • Assuming the numbers are bounded by 32 bits in all languages: here the constraint 10^9 < 2^30 keeps it safe.