# Minimum Flips to Make a OR b Equal to c
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c)
Canonical: https://scaleengineer.com/dsa/problems/minimum-flips-to-make-a-or-b-equal-to-c
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-flips-to-make-a-or-b-equal-to-c/image0.png)

**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

**Constraints:**

* `1 <= a <= 10^9`
* `1 <= b <= 10^9`
* `1 <= c <= 10^9`

# Approaches
## Approach 1: String Conversion and Iteration
This approach first converts the integers into their binary string representations. To compare them bit by bit, the strings are padded with leading zeros to ensure they all have the same length. Then, we can iterate through the characters of the strings, representing the bits, and count the necessary flips based on the problem's logic.
**Time:** O(log N), where N is the maximum value among a, b, and c. The complexity is dominated by the string conversion and the loop that iterates through the bits. This is asymptotically efficient, but carries significant overhead. · **Space:** O(log N), where N is the maximum value among a, b, and c. This space is used to store the binary string representations of the numbers.
**Pros:** May be more intuitive for developers who are less comfortable with direct bitwise manipulation.; The logic is explicit and follows a clear, readable flow.
**Cons:** Inefficient use of memory due to the creation of intermediate strings.; Slower performance because of the overhead associated with string conversions and manipulations compared to direct integer arithmetic.
### Explanation
The core idea is to transform the problem from the domain of integer bitwise operations to string manipulation. By converting `a`, `b`, and `c` to binary strings, we can visually inspect each bit position.

For example, if `a=2`, `b=6`, `c=5`, their binary strings are `"10"`, `"110"`, and `"101"`. The maximum length is 3. We pad the strings to get `a="010"`, `b="110"`, `c="101"`. Now we can compare them position by position:
*   **Position 0 (MSB):** `a='0'`, `b='1'`, `c='1'`. `0|1 = 1`. This matches `c`'s bit. 0 flips.
*   **Position 1:** `a='1'`, `b='1'`, `c='0'`. `1|1 = 1`. This does not match `c`'s bit. To make the result '0', both `a` and `b` must be '0'. We need to flip `a`'s bit and `b`'s bit. 2 flips.
*   **Position 2 (LSB):** `a='0'`, `b='0'`, `c='1'`. `0|0 = 0`. This does not match `c`'s bit. To make the result '1', we need to flip either `a`'s bit or `b`'s bit. 1 flip.

Total flips = 0 + 2 + 1 = 3.

```java
class Solution {
    public int minFlips(int a, int b, int c) {
        String aStr = Integer.toBinaryString(a);
        String bStr = Integer.toBinaryString(b);
        String cStr = Integer.toBinaryString(c);

        int len = Math.max(aStr.length(), Math.max(bStr.length(), cStr.length()));

        // Pad strings with leading zeros
        aStr = String.format("%" + len + "s", aStr).replace(' ', '0');
        bStr = String.format("%" + len + "s", bStr).replace(' ', '0');
        cStr = String.format("%" + len + "s", cStr).replace(' ', '0');

        int flips = 0;
        for (int i = 0; i < len; i++) {
            char bitA = aStr.charAt(i);
            char bitB = bStr.charAt(i);
            char bitC = cStr.charAt(i);

            if (bitC == '0') {
                if (bitA == '1') flips++;
                if (bitB == '1') flips++;
            } else { // bitC == '1'
                if (bitA == '0' && bitB == '0') {
                    flips++;
                }
            }
        }
        return flips;
    }
}
```
### Algorithm
*   Convert the integers `a`, `b`, and `c` to their binary string representations.
*   Determine the maximum length among the three binary strings.
*   Pad the shorter binary strings with leading zeros to make all strings of equal length. This ensures a correct bit-by-bit comparison.
*   Initialize a `flips` counter to zero.
*   Iterate through the strings from left to right (from the most significant bit to the least significant bit).
*   In each position `i`, examine the bits (characters) `bit_a`, `bit_b`, and `bit_c`.
*   Apply the flip logic:
    *   If `bit_c` is '0', then both `bit_a` and `bit_b` must be '0'. Add 1 to `flips` for each of `bit_a` or `bit_b` that is '1'.
    *   If `bit_c` is '1', then `bit_a` or `bit_b` (or both) must be '1'. If both are '0', a single flip is required. Add 1 to `flips`.
*   Return the total `flips` count.

## Approach 2: Direct Bitwise Iteration
This optimal approach works directly on the integer representations of the numbers, using bitwise operations to inspect and compare them bit by bit. It iterates from the least significant bit to the most significant bit, calculating the required flips at each position without any need for intermediate data structures like strings.
**Time:** O(log N), where N is the maximum value of a, b, and c. This corresponds to the number of bits in the largest integer. Since integers in Java have a fixed size (32 bits), the number of iterations is constant, making the effective time complexity O(1). · **Space:** O(1). The algorithm uses only a fixed number of variables for its calculations, regardless of the size of the input integers.
**Pros:** Extremely efficient in terms of both time and space.; Operates directly on the input data without creating new objects, leading to low overhead.; It is the idiomatic and standard way to solve bit manipulation problems.
**Cons:** Requires a solid understanding of bitwise operators (`&`, `|`, `>>`), which might be less familiar to some developers.
### Explanation
The problem can be solved by analyzing the bits of `a`, `b`, and `c` at each position `i`. For the condition `(a | b) == c` to hold, the condition `(a_i | b_i) == c_i` must hold for every bit `i`.

We can iterate through the bits and count the minimum flips required.

*   **Case 1: Target bit `c_i` is 1.**
    To make `a_i | b_i = 1`, we need at least one of `a_i` or `b_i` to be 1. If they are currently `a_i=0` and `b_i=0`, we must perform one flip (either `0->1` in `a` or `b`). If `a_i` or `b_i` is already 1, no flips are needed for this bit. So, we add 1 to flips if `(a_i | b_i) == 0`.

*   **Case 2: Target bit `c_i` is 0.**
    To make `a_i | b_i = 0`, both `a_i` and `b_i` must be 0. If `a_i` is 1, it must be flipped (1 flip). If `b_i` is 1, it must also be flipped (1 flip). So, the number of flips is the sum of the bits of `a` and `b` at this position.

The algorithm iterates using a `while` loop, checking the least significant bit (LSB) in each pass with `& 1`, and then right-shifting the numbers with `>>= 1` to process the next bit.

```java
class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        // Loop until all bits of a, b, and c have been processed.
        while (a > 0 || b > 0 || c > 0) {
            // Get the least significant bit of each number
            int bitA = a & 1;
            int bitB = b & 1;
            int bitC = c & 1;

            if (bitC == 0) {
                // If c's bit is 0, a's and b's bits must both be 0.
                // Add flips for each bit that is 1.
                flips += (bitA + bitB);
            } else { // bitC == 1
                // If c's bit is 1, we need at least one 1 in a or b.
                // If both are 0, we need one flip.
                if (bitA == 0 && bitB == 0) {
                    flips++;
                }
            }

            // Move to the next bit
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return flips;
    }
}
```
### Algorithm
*   Initialize a `flips` counter to 0.
*   Start a loop that continues as long as `a`, `b`, or `c` is greater than 0. This ensures all relevant bits are processed.
*   Inside the loop, extract the least significant bit (LSB) of each number using the bitwise AND operator (`& 1`). Let these be `bitA`, `bitB`, and `bitC`.
*   Apply the core logic:
    *   If `bitC` is 0, the result of `bitA | bitB` must be 0. This requires both `bitA` and `bitB` to be 0. The number of flips needed is `bitA + bitB` (since each '1' bit must be flipped to '0').
    *   If `bitC` is 1, the result of `bitA | bitB` must be 1. A flip is only needed if both `bitA` and `bitB` are 0. In this case, one flip is required.
*   Add the calculated flips for the current bit position to the total `flips` count.
*   Right-shift `a`, `b`, and `c` by one position (`>>= 1`) to process the next bit in the following iteration.
*   Once the loop terminates (all numbers are 0), return the total `flips`.

# Solutions
### Java

```java
class Solution {
public
  int minFlips(int a, int b, int c) {
    int ans = 0;
    for (int i = 0; i < 30; ++i) {
      int x = a >> i & 1, y = b >> i & 1, z = c >> i & 1;
      if ((x | y) != z) {
        ans += x == 1 && y == 1 ? 2 : 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFlips(int a, int b, int c) {
    int ans = 0;
    for (int i = 0; i < 30; ++i) {
      int x = a >> i & 1, y = b >> i & 1, z = c >> i & 1;
      if ((x | y) != z) {
        ans += x == 1 && y == 1 ? 2 : 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int: ans = 0 for i in range(30): x, y, z = a >> i & 1, b >> i & 1, c >> i & 1 if x | y != z: ans += 2 if x == 1 and y == 1 else 1 return ans

```