[Leetcode] 1318. Minimum Flips to Make a OR b Equal to c (Medium)

概述

題目

https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
給定 a, b, c 三個數字，將 a, b 透過 bitflip 方式調整，最終使 a or b = c，求調整最少次數為何

心得

只需要確認 or 操作，耐心模擬完基本上就 AC 了

模擬

思路

先切成二進位，再一位一位確認調整數量，總合即結果

程式

class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        x, y, z = bin(a)[2:], bin(b)[2:], bin(c)[2:]
        n = max(len(x), len(y), len(z))

        # 二進位且長度不同時，短者前面補 0
        for i in range(n-len(x)):
            x = "0" + x
        for i in range(n-len(y)):
            y = "0" + y
        for i in range(n-len(z)):
            z = "0" + z

        cnt = 0
        for i in range(n):
            o, p, q = int(x[i]), int(y[i]), int(z[i])
            if q == o | p:
                continue
            else:
                if q == 0:
                    cnt += o+p
                else:
                    cnt += (o|p)^1
        return cnt

from junaidmansuri 縮減程式，以 pattern 代表 if else 判斷

class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        x, y, z, cnt = bin(a)[2:], bin(b)[2:], bin(c)[2:], 0
        n = max(len(x), len(y), len(z))
        dic = {'010':1, '100':1, '001':1, '110':2}

        o, p, q = x.zfill(n), y.zfill(n), z.zfill(n)
        for i in range(n):
            cnt += dic.get(o[i]+p[i]+q[i], 0)
        return cnt

Complexity

Time Complexity: O(n)
n 個位置的話，每位位置走過一次操作即 n 次

Space Complexity: O(1)
基本上無使用到額外空間

模擬

Bit Manipulation

相同的方式，只是取位以 Bit Manipulation 方式操作，注意 Least Significant Bit (LSB)、最右一位數字的取得方式為 (x & 1)

程式

class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        cnt = 0
        for i in range(32):
            if (a&1) | (b&1) != (c&1):
                if (c&1) == 1:
                    cnt += 1
                else:
                    cnt += (a&1) + (b&1)
            a, b, c = a>>1, b>>1, c>>1
        return cnt

Complexity

Time Complexity: O(n)
n 個位置的話，每位位置走過一次操作即 n 次

Space Complexity: O(1)
基本上無使用到額外空間

一行解

from hrxue；一樣是同樣概念；先確認 a|b 與 c 的差異有多少，做為至少 1 個要翻的計數，再檢查有無 1 and 1 -> 0 的狀況發生，即是要再翻轉一次

程式

class Solution(object):
    def minFlips(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: int
        """
        return bin((a | b) ^ c).count('1') + bin((a & b) & ~c).count('1')