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

Link : https://leetcode.com/problems/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

문제 분석

bit 연산을 하는 것이 좋고 비트 연산을 하더라도 한번에 할 수 있는 것 보다는 별도로 분기를 구현해야 flip하는 횟수를 계산할 수 있는 것으로 생각됩니다.

다음과 같은 sudo code로 로직을 작성해보겠습니다

1. 비트 수만큼 반복

   1. bit a, b, c에 대해서 선언

   2. a or b == c가 불만족하는 경우

      1. bit c가 0이면 bit a, b가 c와 일치하지 않는 수 만큼 flip

      2. bit c가 1이면 1개만 flip(why? a or b 조건이라서)

      3. 다음 비트로 전진 및 2-1번 반복

문제 해결

class Solution {
    fun minFlips(a: Int, b: Int, c: Int): Int {
        var answer = 0
        var curA = a
        var curB = b
        var curC = c


        repeat(32) {
            val bitA = curA and 1
            val bitB = curB and 1
            val bitC = curC and 1

            if ((bitA or bitB) != bitA) {
                answer += (if (bitC == 0) bitA + bitB else 1)
            }

            curA = curA shr 1
            curB = curB shr 1
            curC = curC shr 1
        }

        return answer
    }

}

fun main() {
    val solution = Solution().minFlips(2, 6, 5)
    println(solution)
}

느낀점

오랜만에 비트 연산을 하면서 비트 연산자에 대해서 복기하는 시간이였습니다.

사실 비트 연산 문제는 특정 비트연산을 한번만 사용해서 풀 수 있는가 많은 고민을 하게 되어서 시간이 거기서 오래 걸리는 것 같습니다.

그리고 평소에 잘 사용하지 않는 형식으로 나머지 자리수 계산을 하는 것이라서 항상 안까먹도록 간간히 문제를 풀어야겠다는 생각을 했습니다.