LeetCode Entry

2220. Minimum Bit Flips to Convert Number

11.09.2024 easy 2024 kotlin rust

Bit diff between two numbers manipulation

2220. Minimum Bit Flips to Convert Number easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/731

Problem TLDR

Bit diff between two numbers #easy #bit_manipulation

Intuition


    // 10 1010
    //  7 0111
    //    ** *

To find the bits count there are several hacks: https://stackoverflow.com/a/109025/23151041

https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel


x = (x & 0b1010101010101010101010101010101) + ((x >> 1) & 0b1010101010101010101010101010101);
x = (x & 0b0110011001100110011001100110011) + ((x >> 2) & 0b0110011001100110011001100110011);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

Approach

  • let’s use built-in methods

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun minBitFlips(start: Int, goal: Int) =
        (start xor goal).countOneBits()



    pub fn min_bit_flips(start: i32, goal: i32) -> i32 {
        (start ^ goal).count_ones() as i32
    }



    int minBitFlips(int start, int goal) {
        return __builtin_popcount(start ^ goal);
    }