[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=2025-11-08

LeetCode - Minimum One Bit Operations to Make Integers Zero

문제 유형: 그레이 코드, 비트 조작

문제 난이도: Hard

 

문제

Given an integer n, you must transform it into 0 using the following operations any number of times:

• Change the rightmost (0th) bit in the binary representation of n.
• Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.

 

정수 n이 주어진다. 당신은 아래 두 연산을 몇 번이고 시행하여 n을 0으로 변환해야 한다:

- 이진 표현에서의 가장 오른쪽 비트(0번째)를 바꾼다.

- i-1번째가 1이고, i-2 ~ 0번째까지 나머지가 0인 경우, i번째 비트를 바꾼다.

 

n을 0으로 바꾸기 위한 최소한의 연산수를 구하시오.

 

풀이

n의 최상위 1비트를 k라 하자. 즉, MSB가 k번 비트라 하자.

아래가 모두 0이고, k번 비트만 1인 경우, 0으로 만드는데 T(k) = 2^(k+1) - 1이 든다.

 

n을 0으로 만들려면, f(n) = T(k) - f(n - 2^k)이다.

우선, MSB를 끄려면 T(k)번의 횟수가 필요하고, n(2^k + (n-2^k))를 0으로 만들어야 한다.

즉, 하위 부분은 방향위 뒤집힌 좌표계로 들어간다.

그래서 남는 부분에 대한 비용은 뒤집어 빼는 형태가 된다.

이 재귀식을 풀면, 각 1비트마다 +-(2^(i+1)-1)이 교대로 더해진다.

 

 

코드

C++

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int res;
        for(res = 0; n > 0; n &= n-1) {
            res = -(res + (n^(n-1)));
        }

        return abs(res);
    }
};