# Number Of Flips Required To Make a|b Equal to c

We 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.

## Table of Contents

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).

Assume`n`

is 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 = 0010`

and`b = 0110`

, so`c = 0101`

;

After flips `a`

will be `0001`

and `b`

will be `0100`

.

### Algorithm

- Initialize
`ans`

variable to`0`

. - Loop through, in the range from
`0`

to`31`

.- Initialize
`bitA`

= (^{a}⁄_{2i}) & 1`bitA`

= (^{b}⁄_{2i}) & 1`bitA`

= (^{c}⁄_{2i}) & 1

- Initialize
- If (
`bitA | bitB`

) is not the same as`bitC`

, then- If
`bitC`

is 0- If
`bitA = 1`

and`bitB = 1`

, then increase`ans`

by`2`

, otherwise - Increase
`ans`

by`1`

,

- If
- Increase
`ans`

by`1`

- 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 : 3
```

### C++

```
#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 : 3
```

We 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 : 3
```

### TypeScript

```
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 : 3
```

We 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 : 3
```

## Complexity analysis

### Time complexity

This takes

complexity, as we are comparing bit values in each integer.*log*(*n*)

### Space complexity

The space complexity is

. No additional space is allocated.*O*(1)

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.