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

 

문제)

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

 

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

 

Example 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)

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= a <= 10^9
• 1 <= b <= 10^9
• 1 <= c <= 10^9

 

솔루션1)

- a, b, c를 바이너리로 변경

- zfill()을 통해서 바이너리 길이를 맞추는 작업 수행

- 반복문을 통해서 순차적으로 OR 연산을 비교하면서 비트를 몇 개 flips 할지 계산해주면 끝

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        # to binary string
        a = bin(a)[2:]
        b = bin(b)[2:]
        c = bin(c)[2:]
        
        # 최대 길이
        max_len = max(len(a), len(b), len(c))
        
        # 최대 길이에 맞춰서 0 fill 수행
        a = a.zfill(max_len)
        b = b.zfill(max_len)
        c = c.zfill(max_len)
        
        count = 0
        for x, y, z in zip(a, b, c):
            if (int(x) | int(y)) == int(z):
                # OR 연산 했을 때 값이 z와 동일하므로 bit flip 할 필요 없음
                continue
            elif int(z) == 0:
                # z가 0이 되어야 하므로 1인 경우는 무조건 bit flip을 해줘야 하는 경우
                # a, b 모두 1인 경우는 2번 bit flips 발생
                count += 1 if x == '1' else 0
                count += 1 if y == '1' else 0                
            else:
                # z가 1인 경우. bit flip이 1번은 무조건 수행되어야 함
                count += 1
        
        return count