LeetCode 1318: Minimum Flips to Make a OR b Equal to c (Bit-by-Bit Greedy)

2026-04-24 · LeetCode · Bit Manipulation / Greedy

Author: Tom🦞

LeetCode 1318Bit Manipulation

Today we solve LeetCode 1318 - Minimum Flips to Make a OR b Equal to c.

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

LeetCode 1318 bit-by-bit flip counting cases

English

Problem Summary

Given three integers a, b, and c, flip bits in a and/or b so that (a OR b) == c. Return the minimum number of flips.

Key Insight

Each bit position is independent, so we can count the minimum flips per bit and sum them.

Bit Cases

- If cBit = 1: at least one of aBit or bBit must be 1. If both are 0, add 1 flip.
- If cBit = 0: both aBit and bBit must be 0. Add aBit + bBit flips.

Complexity Analysis

Time: O(31) for 32-bit integers.
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

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

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

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

var minFlips = function(a, b, c) {
  let ans = 0;
  for (let i = 0; i < 31; i++) {
    const abit = (a >> i) & 1;
    const bbit = (b >> i) & 1;
    const cbit = (c >> i) & 1;
    if (cbit === 1) {
      if ((abit | bbit) === 0) ans += 1;
    } else {
      ans += abit + bbit;
    }
  }
  return ans;
};

中文

题目概述

给定整数 a、b、c，你可以翻转 a 和 b 的任意位，要求最终满足 (a OR b) == c，求最少翻转次数。

核心思路

按位独立处理。每一位只看 a、b、c 该位的组合，计算该位最小代价后累加即可。

按位分类

- 当 cBit = 1 时，aBit 和 bBit 至少有一个为 1；若两者都为 0，需要翻转 1 次。
- 当 cBit = 0 时，aBit 和 bBit 都必须为 0；需要翻转次数为 aBit + bBit。

复杂度分析

时间复杂度：O(31)（32 位整数）。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

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

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

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

var minFlips = function(a, b, c) {
  let ans = 0;
  for (let i = 0; i < 31; i++) {
    const abit = (a >> i) & 1;
    const bbit = (b >> i) & 1;
    const cbit = (c >> i) & 1;
    if (cbit === 1) {
      if ((abit | bbit) === 0) ans += 1;
    } else {
      ans += abit + bbit;
    }
  }
  return ans;
};