Leetcode[day22] - Bitwise AND of Numbers Range

 

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Input: [5,7]
Output: 4

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - m과 n이 주어질 때, m과 n 사이의 모든 숫자에 대한 AND 연산자에 대한 값을 구하는게 문제이다.

 - 처음에는 O(N)으로 m~n까지의 모든 숫자에 대한 AND 연산을 했는데, 이럴 경우 시간초과가 일어난다.

 - 이런식으로 풀었는데, 해당 로직이 없어짐.

 - 그래서 정답을 찾아보기로 함.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 어떻게 빠른 시간에 정답을 찾을 수 있을까?

 

 

3. 다른 사람이 작성한 알고리즘 보기

 

https://www.youtube.com/watch?v=SLm32aRonv4

 

4. 해당 알고리즘을 보고 배운 점

 

5. 해당 알고리즘을 보고 작성한 알고리즘

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while(m!=n){
            m = m >> 1;
            n = n >> 1;
            shift++;
        }
        
        return n << shift;
    }
}

 

6. 결과

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3308/

Account Login - LeetCode