1318. Minimum Flips to Make a OR b Equal to c

leetcode medium

#bit-manipulation#csharp#leetcode#medium

Task

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 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)

C# solution

matched/original

public class Solution {
    public int MinFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
}

JavaScript solution

matched/original

var minFlips = function(a, b, c) {
    let answer = 0;
    while (a !== 0 || b !== 0 || c !== 0) {
        if ((c & 1) === 1) {
            if ((a & 1) === 0 && (b & 1) === 0) {
                answer++;
            }
        } else {
            answer += (a & 1) + (b & 1);
        }
        a >>= 1;
        b >>= 1;
        c >>= 1;
    }
    return answer;
};

Python solution

matched/original

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        answer = 0
        while a != 0 or b != 0 or c != 0:
            if (c & 1) == 1:
                if (a & 1) == 0 and (b & 1) == 0:
                    answer += 1
            else:
                answer += (a & 1) + (b & 1)
            a >>= 1
            b >>= 1
            c >>= 1
        return answer

Go solution

matched/original

func minFlips(a int, b int, c int) int {
    answer := 0
    for a != 0 || b != 0 || c != 0 {
        if (c & 1) == 1 {
            if (a & 1) == 0 && (b & 1) == 0 {
                answer++
            }
        } else {
            answer += (a & 1) + (b & 1)
        }
        a >>= 1
        b >>= 1
        c >>= 1
    }
    return answer
}

Explanation

Algorithm

Инициализируйте переменную answer как 0, которая будет использоваться для отслеживания минимального количества необходимых переворотов.

Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).

Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎