Minimum Flips to Make a OR b Equal to c

Medium
424.

Minimum Flips to Make a OR b Equal to c

Minimum Flips to Make a OR b Equal to c is a medium coding problem on bit manipulation, asked in Amazon, Google and Adobe interviews.

Given three non-negative integers a, b and c, return the minimum number of bit flips — each flip changes one bit of a or of b — needed to make (a OR b) == c.

Example 1

Input
a = 2, b = 6, c = 5
Output
3

Example 2

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

Example 3

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

Constraints

  • 0 <= a, b, c <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var minFlips = function(a, b, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Flips to Make a OR b Equal to c — Problem & Solution

Minimum Flips to Make a OR b Equal to c solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Flips to Make a OR b Equal to c is a medium coding problem on bit manipulation, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Bit Manipulation
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given three non-negative integers a, b and c, return the minimum number of bit flips — each flip changes one bit of a or of b — needed to make (a OR b) == c.

Example 1

Input: a = 2, b = 6, c = 5
Output: 3

Example 2

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

Example 3

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

Constraints

  • 0 <= a, b, c <= 1000000000

Hints for Minimum Flips to Make a OR b Equal to c

  1. Hint 1

    Handle each bit position on its own — flips at different positions never interact.

  2. Hint 2

    If the target bit of c is 0, every set bit among a and b at that position must be cleared: 0, 1 or 2 flips.

  3. Hint 3

    If it is 1, you need at least one set bit there — that costs a flip only when both are 0.

How to solve Minimum Flips to Make a OR b Equal to c

Bit positions are independent: a target 0 needs every set bit among a, b cleared (0–2 flips); a target 1 needs one flip only when both are 0.

Approach

  1. For each bit: if c's bit is 0, add a_bit + b_bit; else add 1 if both are 0.

Why it works

OR is computed per position, and flips at one position never affect another, so the minimum is the sum of per-position minima.

Complexity

  • Time — O(31)
  • Space — O(1)

Pitfalls

  • When the target is 1 and exactly one input bit is set, no flip is needed.

Reference solution

Python

def minFlips(a: int, b: int, c: int) -> int:
    flips = 0
    for bit in range(31):
        ab = (a >> bit) & 1
        bb = (b >> bit) & 1
        cb = (c >> bit) & 1
        if cb == 0:
            flips += ab + bb
        elif ab == 0 and bb == 0:
            flips += 1
    return flips

Java

public static int minFlips(int a, int b, int c) {
    int flips = 0;
    for (int bit = 0; bit < 31; bit++) {
        int ab = (a >> bit) & 1;
        int bb = (b >> bit) & 1;
        int cb = (c >> bit) & 1;
        if (cb == 0) flips += ab + bb;
        else if (ab == 0 && bb == 0) flips += 1;
    }
    return flips;
}

C++

int minFlips(int a, int b, int c) {
    int flips = 0;
    for (int bit = 0; bit < 31; bit++) {
        int ab = (a >> bit) & 1;
        int bb = (b >> bit) & 1;
        int cb = (c >> bit) & 1;
        if (cb == 0) flips += ab + bb;
        else if (ab == 0 && bb == 0) flips += 1;
    }
    return flips;
}

JavaScript

var minFlips = function(a, b, c) {
    let flips = 0;
    for (let bit = 0; bit < 31; bit++) {
        const ab = (a >> bit) & 1;
        const bb = (b >> bit) & 1;
        const cb = (c >> bit) & 1;
        if (cb === 0) flips += ab + bb;
        else if (ab === 0 && bb === 0) flips += 1;
    }
    return flips;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation