[Leetcode 3133번 문제] 3133. Minimum Array End

문제 상황

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].

n과 x가 주어진다, 배열을 만들어야한다 정수배열 n의 크기를 갖는 nums를 만든다.

그 특징은 왼쪽보다 오른쪽이 항상 크다.

nums의 배열의 모든 요소 사이의 AND가 x이다.

모든 가능한 nums[n - 1]의 값중 가장 작은 값을 리턴하라.

입력

• 1 <= n, x <= 10 ^ 8

출력

nums[n - 1]의 값중 가장 작은 값을 long long으로 리턴

과정

일단 x는 항상 어떤 배열 nums의 첫번째 요소는 항상 x다.

x보다 작은수가 첫번째 요소라면 모든 nums의 and operation이 전부 x일 수 없고

x보다 큰 수가 첫번째 요소일 때는

모든 nums의 요소의 and가 x이면서 길이가 n인 배열을 만들었다면

그 배열의 첫번째 요소에 x를 추가하고 길이를 배열의 마지막요소를 pop할 경우 동시에 길이가 n이고 and가 x인 배열이 만들어지고 마지막 요소의 값이 작아질 수 있어서. 가장 작은 마지막요소라는 전제에 부합하지 않기 때문이다.

그리고 생각해보았을때, n이라는 특성은 x로부터 시작하는 수를 비트화 했을 때 0인 자리들만을 가지고 n의 비트화된 수를 적용하는 것과 같다.

예를들어 x가 101100(2)이라고 라고할때.

x를 64비트의 배열로 바꾼다

[0, 0, 0, … , 0, 1, 0, 1, 1, 0, 0]

더 직관적으로 자리만을 보기위해 (비트, 인덱스)로 바꿔보면

[(0, 1), (0, 2) … (1, 59), (0, 60), (1, 61), (1, 62), (0, 63), (0, 64)] 형태로 표현될 것이고. 여기서 1인 비트들은 생각해보면 앞으로도 절대 바뀔일이 없다. 그래서 이들을 제외한다.

[(0, 1), (0, 2) … , (0, 60), (0, 63), (0, 64)]으로 바뀐다. 그럼 단순 이 배열만 보고 여기서 nums에서 두번쨰 요소가 뭐가될지를 생각해보면.

[(0, 1), (0, 2) … , (0, 60), (0, 63), (1, 64)] 이렇게 될것이다. 즉 가장 작은 비트가 1인상태로.

만약 nums의 3번째를 알고싶다면

[(0, 1), (0, 2) … , (0, 60), (1, 63), (0, 64)] 이라고 할 수 있다. 즉 시작부터 1인 비트들을 제외하고 원하는 순서 n을 특수한 배열에서 비트화하면 되는 것이다.

이렇게 생각하면. 주어진 문제의 답을 쉽게 구할 수 있다.

알고리즘

class Solution {
public:
    long long minEnd(int n, int x) {
        vector<int> nums (65, 0);
        int idx = 64;
        n--;
        while (x)
        {
            nums[idx] = x & 1;
            x >>= 1;
            idx--;
        }
        idx = 64;
        while (n)
        {
            while (nums[idx])
            {
                idx--;
            }
            nums[idx] = n & 1;
            n >>= 1;
            idx--;
        }
        long long answer = 0;
        for (int i = 0; i <= 64; i++)
        {
            answer |= nums[i];
            answer <<= 1;
        }
        return answer >> 1;
    }
};