Number Of Flips Required To Make a|b Equal to c
6 min readWe need to write a program with minimum flips to make the two bits’ OR operation equal a number. If you understand the OR operations clearly, this problem will be a good challenge for your skills.
If you understand the OR operations clearly, this problem will be a good challenge for your skills. Make sure you have a clear understanding of OR before moving on.
Introduction
In this question, we will flip the bits to make two numbers equal to the third number.
Let’s see how to achieve this using the OR operator.
Problem statement
We need to write a program with minimum flips to make the two bits’ OR operation equal a number.
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips, a = 1 , b = 4 , c = 5 such that (a OR b == c).
Assumenis non-negative. Use the|operator to achieve this.
Solution
We have three positives numbers, a, b, and c. We must find the minimum flips required in some bits of a, b to make (a OR (b == c)). Here we are considering Bitwise OR operation. The flip operation consists of changing any single bit from 1 to 0 or changing the bit from 0 to 1 in their binary representation.
If,a = 0010andb = 0110, soc = 0101;
After flips a will be 0001 and b will be 0100.
Algorithm
- Initialize
ansvariable to0. - Loop through, in the range from
0to31.- Initialize
bitA= (a⁄2i) & 1bitA= (b⁄2i) & 1bitA= (c⁄2i) & 1
- Initialize
- If (
bitA | bitB) is not the same asbitC, then- If
bitCis 0- If
bitA = 1andbitB = 1, then increaseansby2, otherwise - Increase
ansby1,
- If
- Increase
ansby1
- If
- Return
ans
Java
class MinFlips {
private static int helper(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int bitC = ((c >> i) & 1);
int bitA = ((a >> i) & 1);
int bitB = ((b >> i) & 1);
if ((bitA | bitB) != bitC) {
if (bitC == 0) {
if (bitA == 1 && bitB == 1) {
ans += 2;
} else {
ans += 1;
}
} else {
ans += 1;
}
}
}
return ans;
}
public static void main(String[] args) {
int a = 2;
int b = 6;
int c = 5;
System.out.println("Min Flips required to make two numbers equal to third is : " + helper(a, b, c));
}
}
// Output : Min Flips required to make two numbers equal to third is : 3
We can further simplify this code into a single line shown below.
class MinFlips {
private static int helper(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int bitC = ((c >> i) & 1);
int bitA = ((a >> i) & 1);
int bitB = ((b >> i) & 1);
if ((bitA | bitB) != bitC) {
ans += (bitC == 0) ? (bitA == 1 && bitB == 1) ? 2 : 1 : 1;
}
}
return ans;
}
public static void main(String[] args) {
int a = 2;
int b = 6;
int c = 5;
System.out.println("Min Flips required to make two numbers equal to third is : " + helper(a, b, c));
}
}Python
def MinFlips(a,b,c):
ans=0
for i in range(0,32):
bitC = ((c >> i) & 1)
bitA = ((a >> i) & 1)
bitB = ((b >> i) & 1)
if((bitA | bitB) != bitC):
if(bitC == 0):
if(bitA == 1 and bitB == 1):
ans=ans+2
else:
ans=ans+1
else:
ans=ans+1
return ans
a=2
b=6
c=5
print("Min Flips required to make two numbers equal to third is : ",MinFlips(a,b,c))We can further simplify this code into a single line shown below.
def helper(a,b,c):
ans=0
for i in range(0,32):
bitC = ((c >> i) & 1)
bitA = ((a >> i) & 1)
bitB = ((b >> i) & 1)
if((bitA | bitB) != bitC):
ans+=2 if (bitC==0) else (1 if (bitA == 1 and bitB == 1) else 1)
return ans
a=2
b=6
c=5
print("Min Flips required to make two numbers equal to third is : ",helper(a,b,c))JavaScript
const MinFlips = (x, y, z) => {
function helper (a, b, c) {
let ans = 0;
for(let i = 0; i < 32; i++) {
let bitC = ((c >> i) & 1);
let bitA = ((a >> i) & 1);
let bitB = ((b >> i) & 1);
if((bitA | bitB) !== bitC) {
if(bitC === 0) {
if(bitA === 1 && bitB === 1) {
ans += 2;
}else {
ans += 1;
}
}else {
ans += 1;
}
}
}
return ans;
}
return helper (x, y, z);
}
const a = 2;
const b = 6;
const c = 5
console.log (`Min Flips required to make two numbers equal to third is : ${MinFlips (a, b, c)}`);
// Output : Min Flips required to make two numbers equal to third is : 3
We can further simplify this code into a single line shown below.
const MinFlips = (x, y, z) => {
function helper (a, b, c) {
let ans = 0;
for(let i = 0; i < 32; i++) {
let bitC = ((c >> i) & 1);
let bitA = ((a >> i) & 1);
let bitB = ((b >> i) & 1);
if((bitA | bitB) !== bitC) {
ans += (bitC === 0) ? (bitA === 1 && bitB === 1) ? 2 : 1 : 1;
}
}
return ans;
}
return helper (x, y, z);
}
const a = 2;
const b = 6;
const c = 5
console.log (`Min Flips required to make two numbers equal to third is : ${MinFlips (a, b, c)}`);
//Output : Min Flips required to make two numbers equal to third is : 3C++
#include <iostream>
using namespace std;
int helper(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int bitC = ((c >> i) & 1);
int bitB = ((b >> i) & 1);
int bitA = ((a >> i) & 1);
if ((bitA | bitB) != bitC) {
if (bitC == 0) {
if (bitA == 1 && bitB == 1) {
ans += 2;
} else {
ans += 1;
}
} else {
ans += 1;
}
}
}
return ans;
}
int main() {
int a = 2, b = 6, c = 5;
cout << "Min Flips required to make two numbers equal to third is : " << helper(a, b, c);
return 0;
}
//Output : Min Flips required to make two numbers equal to third is : 3We can further simplify this code into a single line shown below.
#include <iostream>
using namespace std;
int helper(int a, int b, int c) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int bitC = ((c >> i) & 1);
int bitB = ((b >> i) & 1);
int bitA = ((a >> i) & 1);
if ((bitA | bitB) != bitC) {
ans += (bitC == 0) ? (bitA == 1 && bitB == 1) ? 2 : 1 : 1;
}
}
return ans;
}
int main() {
int a = 2, b = 6, c = 5;
cout << "Min Flips required to make two numbers equal to third is : " << helper(a, b, c);
return 0;
}
// Output : Min Flips required to make two numbers equal to third is : 3TypeScript
export const MinFlips = (x: number, y: number, z: number): number => {
function helper(a: number, b: number, c: number): number {
let ans: number = 0;
for (let i = 0; i < 32; i++) {
let bitC: number = ((c >> i) & 1);
let bitA: number = ((a >> i) & 1);
let bitB: number = ((b >> i) & 1);
if ((bitA | bitB) !== bitC) {
if (bitC === 0) {
if (bitA === 1 && bitB === 1) {
ans += 2;
} else {
ans += 1;
}
} else {
ans += 1;
}
}
}
return ans;
}
return helper(x, y, z);
}
const a: number = 2;
const b: number = 6;
const c: number = 5
console.log(`Min Flips required to make two numbers equal to third is : ${MinFlips(a, b, c)}`);
// Output : Min Flips required to make two numbers equal to third is : 3We can further simplify this code into a single line shown below.
export const MinFlips = (x: number, y: number, z: number): number => {
function helper(a: number, b: number, c: number): number {
let ans: number = 0;
for (let i = 0; i < 32; i++) {
let bitC: number = ((c >> i) & 1);
let bitA: number = ((a >> i) & 1);
let bitB: number = ((b >> i) & 1);
if ((bitA | bitB) !== bitC) {
ans += (bitC === 0) ? (bitA === 1 && bitB === 1) ? 2 : 1 : 1;
}
}
return ans;
}
return helper(x, y, z);
}
const a: number = 2;
const b: number = 6;
const c: number = 5
console.log(`Min Flips required to make two numbers equal to third is : ${MinFlips(a, b, c)}`);
//Output : Min Flips required to make two numbers equal to third is : 3Complexity analysis
Time complexity
This takes log(n) complexity, as we are comparing bit values in each integer.
Space complexity
The space complexity is O(1). No additional space is allocated.