Minimum Flips to Make a OR b Equal to c

Problem Statement:-

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.

Link: https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/description/

Problem Explanation with 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

Constraints

• 1 <= a <= 10^9

• 1 <= b <= 10^9

• 1 <= c <= 10^9

Intuition:-

• If we need bit to be 0, then we need to flip both a and b if they are 1.

• If we need bit to be 1, then we need to flip either a or b if they are 0.

• These are the only two cases we need to consider for minimum flips.

Solution:-

• Define a function to pad the binary strings with 0s to make them of equal length.

• Convert a, b and c to binary strings using bin() function.

• Pad a, b and c to make them of equal length using the function defined in step 1.

• Iterate over the strings from right to left and check the following:

• If c[i] == '0', then check if a[i] == '1' and b[i] == '1'. If yes, then we need to flip both a and b. So, increment ans by 1 for each flip i.e. increment ans by 2.

• If c[i] == '1', then check if a[i] == '0' and b[i] == '0'. If yes, then we need to flip either a or b. So, increment ans just by 1.

• Return ans.

Code:-

JAVA Solution

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 l = Math.max(Math.max(aStr.length(), bStr.length()), cStr.length());
        aStr = pad(aStr, l);
        bStr = pad(bStr, l);
        cStr = pad(cStr, l);

        int i = l - 1;
        int ans = 0;
        while (i >= 0) {
            if (cStr.charAt(i) == '0') {
                if (aStr.charAt(i) == '1') {
                    ans += 1;
                }
                if (bStr.charAt(i) == '1') {
                    ans += 1;
                }
            } else {
                if (aStr.charAt(i) == '0' && bStr.charAt(i) == '0') {
                    ans += 1;
                }
            }
            i -= 1;
        }
        return ans;
    }

    private String pad(String x, int l) {
        StringBuilder sb = new StringBuilder(x);
        while (sb.length() < l) {
            sb.insert(0, "0");
        }
        return sb.toString();
    }
}

Python Solution

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        def pad(x,l):
            x = ("0"*(l-len(x)))+x
            return x
        a = str(bin(a))[2:]
        b = str(bin(b))[2:]
        c = str(bin(c))[2:]
        l = max(len(a),len(b),len(c))
        a = pad(a,l)
        b = pad(b,l)
        c = pad(c,l)

        i = l-1
        ans = 0
        while i >= 0:
            if c[i] == '0':
                if a[i] == '1':
                    ans += 1
                if b[i] == '1':
                    ans += 1
            else:
                if a[i] == '0' and b[i] == '0':
                    ans += 1
            i -= 1
        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(log(max(a,b,c))) as we are iterating over the binary strings of a, b and c.

SPACE:-

The space complexity is O(log(max(a,b,c))) as we are storing the binary strings of a, b and c.

References:-

• Bit Manipulation

Connect with me:-

• Twitter

• Github

• LinkedIn