Minimum Flips to Make a OR B Equal to C Problem

Problem

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation). Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Examples

Example 1:

Input:
a = 2, b = 6, c = 5
Output:
 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (`a` OR `b` == `c`)

Example 2:

Input:
a = 4, b = 2, c = 7
Output:
 1

Example 3:

Input:
a = 1, b = 2, c = 3
Output:
 0

Solution

Method 1 – Bitwise Greedy Flip Counting

Intuition

The algorithm efficiently counts the minimum number of bit flips needed by examining each bit position independently. For each bit, it determines if a flip is required in a or b to make (a | b) match c, minimizing unnecessary operations.

Approach

1. Iterate through each bit position (0 to 31).
2. For each bit, extract the corresponding bits from a, b, and c.
3. If the target bit in c is 1, flip is needed only if both a and b have 0 at that position.
4. If the target bit in c is 0, flip is needed for every 1 in a and b at that position.
5. Accumulate the total number of flips required.
6. Return the total flips.

Code

Java

class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; i++) {
            int abit = (a >> i) & 1;
            int bbit = (b >> i) & 1;
            int cbit = (c >> i) & 1;
            if (cbit == 1) {
                if (abit == 0 && bbit == 0) flips++;
            } else {
                if (abit == 1) flips++;
                if (bbit == 1) flips++;
            }
        }
        return flips;
    }
}

C++

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; ++i) {
            int abit = (a >> i) & 1;
            int bbit = (b >> i) & 1;
            int cbit = (c >> i) & 1;
            if (cbit == 1) {
                if (abit == 0 && bbit == 0) flips++;
            } else {
                if (abit == 1) flips++;
                if (bbit == 1) flips++;
            }
        }
        return flips;
    }
};

Go

func minFlips(a, b, c int) int {
    flips := 0
    for i := 0; i < 32; i++ {
        abit := (a >> i) & 1
        bbit := (b >> i) & 1
        cbit := (c >> i) & 1
        if cbit == 1 {
            if abit == 0 && bbit == 0 {
                flips++
            }
        } else {
            if abit == 1 {
                flips++
            }
            if bbit == 1 {
                flips++
            }
        }
    }
    return flips
}

Python

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        for i in range(32):
            abit = (a >> i) & 1
            bbit = (b >> i) & 1
            cbit = (c >> i) & 1
            if cbit == 1:
                if abit == 0 and bbit == 0:
                    flips += 1
            else:
                if abit == 1:
                    flips += 1
                if bbit == 1:
                    flips += 1
        return flips

Rust

impl Solution {
    pub fn min_flips(a: i32, b: i32, c: i32) -> i32 {
        let mut flips = 0;
        for i in 0..32 {
            let abit = (a >> i) & 1;
            let bbit = (b >> i) & 1;
            let cbit = (c >> i) & 1;
            if cbit == 1 {
                if abit == 0 && bbit == 0 {
                    flips += 1;
                }
            } else {
                if abit == 1 {
                    flips += 1;
                }
                if bbit == 1 {
                    flips += 1;
                }
            }
        }
        flips
    }
}

TypeScript

class Solution {
    minFlips(a: number, b: number, c: number): number {
        let flips = 0;
        for (let i = 0; i < 32; i++) {
            const abit = (a >> i) & 1;
            const bbit = (b >> i) & 1;
            const cbit = (c >> i) & 1;
            if (cbit === 1) {
                if (abit === 0 && bbit === 0) flips++;
            } else {
                if (abit === 1) flips++;
                if (bbit === 1) flips++;
            }
        }
        return flips;
    }
}

Complexity

• ⏰ Time complexity: O(1), since the number of bits is fixed (32).
• 🧺 Space complexity: O(1), only a few variables are used.