Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)

Teaching Kids Programming: Videos on Data Structures and Algorithms

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0. For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc. Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Example 1:
Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
– Flip the first bit from the right: 1010 -> 1011.
– Flip the third bit from the right: 1011 -> 1111.
– Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:
Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
– Flip the first bit from the right: 011 -> 010.
– Flip the second bit from the right: 010 -> 000.
– Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:
0 <= start, goal <= 10^9

Minimum Bit Flips to Convert Number (Hamming Distance)

The Hamming Distance is the number of the difference (bits, symbols) between two numbers or strings. Here we want to find out the min number of flips, which is the same as the number of different bits, aka, the Hamming Distance. We can use the XOR (Exclusive OR) and find out the 1’s in the result.

We can use the bin function to convert a number to binary string for example, bin(15) gives “0b1111” and then we can count the ‘1’s using the count function. However, converting to binary takes O(LogN), and then we need to perform a linear scan on the result binary string, so the time complexity is O(LogN). And space complexity is O(LogN) as we need to store the binary string.

1
2
3
4

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        x = start ^ goal
        return bin(x).count('1')

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        x = start ^ goal
        return bin(x).count('1')

A faster/efficient approach would be to use the bit operation, each iteration we removes the LSB (least significant bit which is one) using x &= (x – 1). The time complexity is O(LogN) if the number N is unbounded, otherwise O(1) constant. Using bit maths is certainly quicker than performing a count on the binary string. The space complexity for this approach is O(1) constant.

1
2
3
4
5
6
7
8

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        x = start ^ goal
        ans = 0
        while x:
            x = x & (x - 1)
            ans += 1
        return ans

class Solution:
    def minBitFlips(self, start: int, goal: int) -> int:
        x = start ^ goal
        ans = 0
        while x:
            x = x & (x - 1)
            ans += 1
        return ans

Hamming Weight / Hamming Distance Algorithms

Here are the posts related to Hamming Distance (XOR, The number of different bits):

• A faster approach to count set bits in a 32-bit integer
• Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1’s Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

–EOF (The Ultimate Computing & Technology Blog) —