3314 - Construct the Minimum Bitwise Array I

info

문제 보기: 3314 - Construct the Minimum Bitwise Array I
소요 시간: 11분 5초
풀이 언어: java
체감 난이도: 2️⃣
리뷰 횟수: ✅

풀이 키워드

스포주의

구현 비트 조작

풀이 코드

info

메모리: 46250 KB
시간: 18 ms

class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int[] ans = new int[nums.size()];
        for (int i = 0; i < nums.size(); ++i) {
            for (int x = 0; x < 1001; ++x) {
                if((x | (x+1)) == nums.get(i)) {
                    ans[i] = x;
                    break;
                }
                ans[i] = -1;
            }
        }

        return ans;
    }
}

풀이 해설

constraint가 허접해서 그냥 BF 돌렸는데... 아무래도 비트 트릭이 있어보여 추가로 알아보았다.

📌 최적화 가능 요소

졸려서 n줄 요약 쓰자면:

1. x OR x+1 = n

2. x는 소수라서 x+1의 LSB는 무조건 0

3. 올림되면서 x의 LSB 0이 1로 바뀜

4. 둘이 OR 연산시 x의 LSB 0만 1로 바뀜

5. 정답은 x의 LSB 0을 1로 바꾼 값

즉, 하단과 같다.

\begin{aligned} x &= 1011_2 \quad (11) \\ x + 1 &= 1100_2 \quad (12) \\ x \mid (x + 1) &= 1011_2 \mid 1100_2 \\ &= 1111_2 \quad (15) \end{aligned}

📌 최적화 후 코드

메모

쉽지만 생각할 거리 있는 문제

풀이 키워드​

풀이 코드​

풀이 해설​

📌 최적화 가능 요소​

📌 최적화 후 코드​

메모​

풀이 키워드

풀이 코드

풀이 해설

📌 최적화 가능 요소

📌 최적화 후 코드

메모