알고리즘/LeetCode
1318. Minimum Flips to Make a OR b Equal to c
앤테바
2022. 12. 24. 23:49
반응형
문제)
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
반응형