Sponsored
Sponsored
The simplest way to determine the different bits between two numbers is to use the XOR operation. XORing two bits will yield 1 if the bits are different and 0 if they are the same. Thus, XORing two numbers will produce a number with bits set at positions where the input numbers have different bits. Counting the number of 1s in this result will give the number of flips required.
Time Complexity: O(n) where n is the number of bits in the maximum of the two numbers, as you may have to check each bit once.
Space Complexity: O(1) as no additional space is used.
1def min_flips(start, goal):
2 xor = start ^ goal
3 count = 0
4 while xor:
5 count += xor & 1
6 xor >>= 1
7 return count
8
9start, goal = 10, 7
10print(min_flips(start, goal)) # Output: 3The Python code calculates the XOR, then counts set bits (1s) in the result using bitwise manipulation.
Many languages offer built-in functions to count the number of set bits (ones) in a binary number. Utilizing these handy functions can make our solution more concise and often more efficient. The bitwise XOR is computed between the two numbers, and the solution boils down to counting the number of set bits in the result.
Time Complexity: O(1) on systems where built-ins are optimized.
Space Complexity: O(1) since we use no additional resources.
class MinFlips {
public static int MinFlipsCalc(int start, int goal) {
return CountBitsPopCount(start ^ goal);
}
static int CountBitsPopCount(int num) {
return Convert.ToString(num, 2).Count(c => c == '1');
}
static void Main(string[] args) {
int start = 10, goal = 7;
Console.WriteLine(MinFlipsCalc(start, goal)); // Output: 3
}
}In C#, we can convert the XOR-ed result to a string in binary format, then use LINQ to count '1's, providing an efficient solution.