[LeetCode 75] Medium - 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

Hint 1

 

Check the bits one by one whether they need to be flipped.

 

문제 해설

주어진 문제는 **세 개의 양의 정수 aaa, bbb, ccc**가 주어질 때, 비트 OR 연산을 통해 a OR b = c를 만족시키기 위해 a와 b의 비트를 뒤집어야 하는 최소 횟수를 구하는 문제입니다.

---

문제 조건

1. a, b, c는 양의 정수로 주어집니다.
2. 각 비트에 대해:
   • 비트를 1에서 0으로 또는 0에서 1로 바꾸는 "플립(flip)" 연산이 가능합니다.
3. 목표는 a OR b = c 를 만족시키기 위해 필요한 최소 플립 횟수를 계산하는 것입니다.

 

 

Code

 

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0  # 플립 횟수 초기화

        # 모든 비트가 0이 될 때까지 반복
        while a > 0 or b > 0 or c > 0:
            # 각 숫자의 현재 비트를 추출
            bit_a = a & 1
            bit_b = b & 1
            bit_c = c & 1

            # 조건에 따라 플립 계산
            if bit_c == 1:
                # c의 비트가 1이면: a와 b 중 적어도 하나가 1이어야 함
                if bit_a == 0 and bit_b == 0:
                    flips += 1  # 둘 다 0이면 1번 플립 필요
            else:
                # c의 비트가 0이면: a와 b가 모두 0이어야 함
                flips += (bit_a + bit_b)  # 각 비트를 0으로 만들기 위한 플립 횟수

            # 다음 비트를 처리하기 위해 시프트
            a >>= 1 # a = a >> 1
            b >>= 1
            c >>= 1

        return flips  # 최소 플립 횟수 반환

 

 

 

두번째 시도

 

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        # or
        # 0이 되려면, 둘다 0이어야함
        # 1이 되려면, 둘중 하나만 1이어도 됨
        flip = 0
        # 모든 비트가 0이 될 때까지 반복
        # while a>0 and b>0 and c>0: <== 안됨
        # 왜냐하면, a,b,c 모두 자리수가 다를수 있기때문에, 
        # 모두가 0이 될때까지 실행되어야 함
        while a>0 or b>0 or c>0:
            bitA = a & 1 # 제일 우측 비트 뽑아냄
            bitB = b & 1
            bitC = c & 1

            if bitC == 1:
                if bitA ==0 and bitB == 0:
                    flip += 1
                # else: # if bitA ==1 or bitB == 1:                
                #     flip += (2-bitA-bitB)
            else: # bitC == 0:
                flip += (bitA+bitB)
            
            a >>= 1 # a = a >> 1
            b >>= 1 
            c >>= 1 
        return flip