👨🏻‍💻

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.

31 Jan 2023 — 5 min read

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⁄_2ⁱ) & 1
  - bitA = (^b⁄_2ⁱ) & 1
  - bitA = (^c⁄_2ⁱ) & 1
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,
- Increase ans by 1
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 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.

Coding Interview Questions Data Structures and Algorithms Bit Manipulation

Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Comments

Related Posts

4 Feb 2024

Paid Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Leetcode 217: Contains Duplicate

3 Feb 2024

Paid Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Leetcode 121: Best Time To Buy and Sell Stock

23 Jun 2023

Paid Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things