[LeetCode] 1611. Minimum One Bit Operations to Make Integers Zero

https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/description/?envType=daily-question&envId=2023-11-30

Minimum One Bit Operations to Make Integers Zero - LeetCode

1611. Minimum One Bit Operations to Make Integers Zero - Hard

 

이진법으로 표현된 수를 정해진 규칙에 따라 0으로 만드는 최소 횟수를 구하는 문제.

규칙은 다음과 같다.

1. 1의 자리의 수를 바꾼다.

2. 어떤 자리의 바로 오른쪽 수가 1이고, 그 오른쪽에 있는 모든 수가 0일때, 그 자리의 수를 바꾼디.

 

이런 문제가 다 그렇듯, 정해진 규칙이 있게 된다.

몇가지를 수를 써보면 규칙이 보이는데, DP와 같이 자리수를 줄여가며 풀면 된다.

예를 들어,

 

111011 이 있다고 치면,
1. f(111011(2)) = 63 - f(11011(2))

2. f(11011(2)) = 31 - f(1011(2))
3. f(1011(2)) = 15 - f(011(2))

4. f(011(2)) = f(11(2))

5. f(11(2)) = 3 - f(1(2))

6. f(1(2)) = 1

따라서 구하는 수는 63 - (31 - (15 - (3 - 1))) = 45.

 

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int r = n&1;
        n>>=1;
        for (int i=2; n>0; i++, n>>=1) if (n&1) r = (1<<i) - r - 1;
        return r;
    }
};