Leetcode 1318. Minimum Flips to Make a OR b Equal to c
Problem Description
You are given three positive integers, a
, b
, and c
. Your task is to determine the minimum number of bit flips required to make a OR b
equal to c
. A single flip operation
consists of changing any single bit in the binary representation of a
or b
, such as changing bit 1 to 0 or changing bit 0 to 1.
Walkthrough of an Example
Consider the example where a is 2 (binary 10), b is 6 (binary 110) and c is 5 (binary 101). Here, we cannot directly perform a OR b
to get c
. We would need to change the binary representation of a
from 10 to 01 and b
from 110 to 100. This requires 3 bit flips. Thus, the output is 3.
Approach
The solution employs bitwise operation and bitwise shifting. For each bit from the least significant bit to the most significant bit, it checks if the ith bit of c
is 1 or 0. If it is 1, it checks if both a
and b
have the ith bit as 0, and if so, increments the count. If the bit of c
is 0, it increments the count by checking if a
or b
has the ith bit as 1.
Python Solution
1 2python 3class Solution: 4 def minFlips(self, a: int, b: int, c: int) -> int: 5 # maximum number of bits any positive integer can have 6 max_bits = 30 7 flips = 0 8 # For every bit from least significant to most significant 9 for i in range(max_bits): 10 # If ith-bit of c is 1 11 if (c >> i & 1) == 1: 12 flips += (a >> i & 1) == 0 and (b >> i & 1) == 0 13 else: # If ith-bit of c is 0 14 flips += ((a >> i & 1) == 1) + ((b >> i & 1) == 1) 15 return flips
Java Solution
1 2java 3class Solution { 4 public int minFlips(int a, int b, int c) { 5 int max_bit = 30; 6 int flips = 0; 7 for (int i = 0; i < max_bit; ++i) 8 if ((c >> i & 1) == 1) 9 flips += (a >> i & 1) == 0 && (b >> i & 1) == 0 ? 1 : 0; 10 else 11 flips += ((a >> i & 1) == 1 ? 1 : 0) + ((b >> i & 1) == 1 ? 1 : 0); 12 return flips; 13 } 14}
JavaScript Solution
1 2javascript 3class Solution { 4 minFlips(a, b, c) { 5 let max_bit = 30, flips = 0; 6 for(let i = 0; i < max_bit; ++i) { 7 if((c >> i & 1) === 1) 8 flips += ((a >> i & 1) === 0 && (b >> i & 1) === 0) ? 1 : 0; 9 else 10 flips += ((a >> i & 1) === 1 ? 1 : 0) + ((b >> i & 1) === 1 ? 1 : 0); 11 } 12 return flips; 13 } 14}
C++ Solution
1 2cpp 3class Solution { 4public: 5 int minFlips(int a, int b, int c) { 6 int max_bit = 30, flips = 0; 7 for(int i = 0; i < max_bit; ++i) 8 if((c >> i & 1) == 1) 9 flips += ((a >> i & 1) == 0 && (b >> i & 1) == 0) ? 1 : 0; 10 else 11 flips += ((a >> i & 1) == 1 ? 1 : 0) + ((b >> i & 1) == 1 ? 1 : 0); 12 return flips; 13 } 14};
C# Solution
1 2csharp 3public class Solution { 4 public int MinFlips(int a, int b, int c) { 5 int max_bit = 30, flips = 0; 6 for(int i = 0; i < max_bit; ++i) 7 if((c >> i & 1) == 1) 8 flips += ((a >> i & 1) == 0 && (b >> i & 1) == 0) ? 1 : 0; 9 else 10 flips += ((a >> i & 1) == 1 ? 1 : 0) + ((b >> i & 1) == 1 ? 1 : 0); 11 return flips; 12 } 13}
All the codes in each language follow a similar pattern to solve the problem. The algorithm makes use of bitwise operations.The bitwise operations used here are bitwise shift (>>
) and bitwise AND (&
). Operation c >> i
is bitwise right shift which shifts the bits of c
i
times to the right. The operator (&
) is bitwise AND which takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits.
The solutions in Python, JavaScript, Java, C++, and C# all mirror the same general steps:
-
Use a loop to iterate through each bit from least to most significant (from right to left in the binary representation of the number). The loop runs for a fixed number of iterations -
30
in this case - to cover all possible bits that an integer can have. -
For each bit, shift
c
i
bits to the right and apply bitwise AND with1
. If the result is1
, it means thei-th
bit inc
is1
. Then check: if both thei-th
bit ofa
and thei-th
bit ofb
are0
, increment theflips
counter. -
If the
i-th
bit ofc
is0
(c >> i & 1 == 0
), check: ifi-th
bit ofa
ori-th
bit ofb
is1
, increment theflips
counter for each such occurrence. -
Finally, return the
flips
counter as the total number of bit flips needed to satisfya OR b
equals toc
.
By using these bitwise operations, the problem of calculating the minimum number of bit flips becomes straightforward and efficient. These solutions provide a clear way to handle complex bit manipulation problems.
These solutions will work in Python 3.x, JavaScript (ES6 and later), Java 11 and later, C++11 and later, and C# 7.0 and later. For earlier versions of these languages, you may need to adjust the code for compatibility with the specific language version.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.