문제

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-1]을 만들되 모든 수가 AND연산을 하여 x를 만들어야하고 증가 수열이어야한다.

풀이

일단 전탐은 절대 불가....long범위임;;;

그래서 일단 AND의 특성을 활용

둘다 1이어야 1이나오는 AND연산이므로

x의 이진수 자리에서 0에 해당하는 자리에 n -1 의 이진수를 체워넣으면 된다 (첫번째는 x와 같으므로)

풀이 1

처음 사용한 방법은 Stack을 사용하였다.

n과 x를 2로 나누면서 큰수부터 stack넣었고 차례대로 빼면서 넣었다.


class Solution {
    public long minEnd(int n, int x) {
        Stack<Boolean> xB = toBinary(x);
        Stack<Boolean> nB = toBinary(n-1);
        long result = 0;
        long val = 1;
        while (!nB.isEmpty()) {
            boolean nn = nB.pop();
            if (xB.isEmpty()) {
                if (nn) {
                    result += val;
                }
                val *= 2;
                continue;
            }
            boolean xn = xB.pop();
            while (!xB.isEmpty() && xn) {
                xn = xB.pop();
                val *= 2;
            }
            if(xB.isEmpty()){
                val *= 2;
            }
            if (nn) {
                result += val;
            }
            val *= 2;
        }

        return result + x;
    }

    private Stack<Boolean> toBinary(int num) {
        Stack<Boolean> stack = new Stack<>();

        int pow = 1;

        while( pow*2 <= num) {
            pow *= 2;
        }

        while (pow > 1) {
            if (num >= pow) {
                stack.push(true);
                num -= pow;
            } else {
                stack.push(false);
            }
            pow /= 2;
        }
        stack.push(num == 1);
        return stack;
    }
}

풀이 2

비트 연산자다 보니 shift를 활용하면 더 빠를것이라 생각했다
그래서 <<연산을 통해 계산을 해주었다.
1부터 시작하여 1<==을 하면 2의 n승 값만 나오므로 각 자리수를 구변할 수 있고
number & 1을 할 경우 첫째자리가 무엇인지 판별 가능하다

이를 활용하여 n이 0보다 클때
우선 x의 val의 숫자가 0이 나올때까지 val를 좌로 shift시켜주고
0이 나왔을때 n의 첫째자리숫자가 1이면 result( 가장 작은 답은 항상 x이므로 result는 x로 시작)와 val를 or연산으로 해준다.

이때 (n&1)*val는 n의 첫자리 수가 0일경우 val는 0이 모든 수가 0이 되어 연산결과는 result가 되고

1일 경우 val가 result에 더해진다.

이후 val를 또 이동 시켜주고, n을 >>= 1해줘서 다음 자리수를 확인한다.


class Solution {
    public long minEnd(int n, int x) {
        long result = x;
        n--;
        long val = 1;
        while (n > 0) {
            while ((x & val) != 0) {
                val <<= 1;
            }
            result |= (n&1) * val;
            val <<= 1;
            n >>= 1;
        }
        return result;
    }
}

풀이 시간

15분

체감 난이도

쉽게풀면 쉽게 풀고, 어렵게 하면 또 어렵고;;