Minimum Flips to Make a OR b Equal to c - Practice Coding Problems

Minimum Flips to Make a OR b Equal to c - Problem

Bit Manipulation Medium

Given three positive numbers a, b, and c, return the minimum number of bit flips required to make (a OR b) == c.

A flip operation consists of changing any single bit from 1 to 0 or from 0 to 1 in the binary representation of a number.

The bitwise OR operation returns 1 if at least one of the corresponding bits is 1, otherwise 0.

Input & Output

Example 1 — Basic Case

$ Input: a = 2, b = 7, c = 5

› Output: 2

💡 Note: Binary: a=010, b=111, c=101. Current a|b=111, target=101. Need to flip bits 1 in both a and b to make them 0.

Example 2 — No Flips Needed

$ Input: a = 4, b = 2, c = 6

› Output: 0

💡 Note: Binary: a=100, b=010, c=110. Current a|b=110 equals target c=110, so no flips needed.

Example 3 — Need More 1s

$ Input: a = 1, b = 2, c = 7

› Output: 1

💡 Note: Binary: a=001, b=010, c=111. Current a|b=011, need 111. Must flip bit 2 in either a or b to 1.

Constraints

1 ≤ a, b, c ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Three integers a, b, c with their binary representations

Process

Check each bit position and count required flips

Output

Minimum number of bit flips needed

Key Takeaway

🎯 Key Insight: Check each bit position independently and apply OR operation rules to count minimum flips

Asked in

f Facebook 15 M Microsoft 12 a Amazon 8

The key insight is to process each bit position and apply OR logic rules: when target bit is 1, ensure at least one input is 1; when target bit is 0, both inputs must be 0. Best approach uses bit manipulation to count flips efficiently. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit-by-Bit Comparison	O(log n)	O(1)	Check each bit position individually and count required flips
Optimized Bit Manipulation	O(log n)	O(1)	Use XOR to find mismatched bits and count flips efficiently

Bit-by-Bit Comparison — Algorithm Steps

Step 1: Extract bits at each position for a, b, and c
Step 2: Calculate current OR result
Step 3: Count flips needed based on target bit

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Bits

Get the least significant bit of each number

Check OR Result

Calculate a|b and compare with target c bit

Count Flips

Add required flips based on the difference

Code -

solution.c — C

#include <stdio.h>

int solution(int a, int b, int c) {
    int flips = 0;
    
    // Check each bit position
    while (a > 0 || b > 0 || c > 0) {
        int bitA = a & 1;
        int bitB = b & 1;
        int bitC = c & 1;
        
        int currentOr = bitA | bitB;
        
        if (currentOr != bitC) {
            if (bitC == 1) {
                // Need at least one of a or b to be 1
                flips += 1;
            } else {
                // Need both a and b to be 0
                flips += bitA + bitB;
            }
        }
        
        a >>= 1;
        b >>= 1;
        c >>= 1;
    }
    
    return flips;
}

int main() {
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result = solution(a, b, c);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

We iterate through at most 32 bits (log of maximum integer value)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit-by-Bit Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler