[LeetCode] 3133. Minimum Array End

https://leetcode.com/problems/minimum-array-end/description/?envType=daily-question&envId=2024-11-09

leetcode - Minimum Array End

문제 유형: 비트마스킹

문제 난이도: Medium

 

문제

You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.

Return the minimum possible value of nums[n - 1].

 

배열 nums를 만드시오. n개의 요소들이 오름차순이어야 하고, 모든 요소들을 bitwise AND연산시 x가 되어야 합니다.

nums[n-1]의 가능한 최소값을 구하시오.

풀이

bitset을 만든다.

X비트셋에는 x를 넣어서 이진표현 시켜놓고, 

N비트셋에는 n-1을 넣어서 비트셋으로 표현한다.

ans는 0으로 시작한다.

 

LSB부터 순차적으로 검사한다.

X의 i번째비트가 1이면 1, 0이면 N의 j번째비트(j도0으로시작)번으로 놓는다. 그리고 j를 1 추가한다.

왜냐하면, X의 i번째비트가 1이면, 그 비트는 반드시 1이어야 한다.

그게 아니라면, 0 또는 1이어도 되는데, 확실하게 이전 비트보다 크려면, 다른 인덱스변수 j번째가 더 MSB이기만 하면 된다.

즉, 엄격하게 한 비트씩만 더 크게 해서 구하는 방법이다.

 

최종 ans를 형변환하여 변환한다.

 

코드

C++

class Solution {
public:
    long long minEnd(int n, int x) {
        bitset<64> X(x), N(n-1), ans = 0;
        for(int i = 0, j = 0; i < 56; ++i) {
            ans[i] = (X[i])?1:N[j++];
        }
        return ans.to_ullong();
    }
};