November 24, 2019

#LeetCode: Java Solution of Bitwise AND of Numbers Range problem

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.

Example 1: Input: [5,7], Output: 4
Example 2:Input: [0,1], Output: 0

Reference:

Decimal No.
4-bit Binary No.
0
0
1
1
2
10
3
11
4
100
5
101
6
110
7
111
8
1000
9
1001
10
1010
11
1011
12
1100
13
1101
14
1110
15
1111
16
0001 0000
17
0001 0001

Algorithm
1. FYI, as per the binary logic 0 AND 0 is 0, 0 AND 1 is 0, 1 AND 0 is 0, 1 AND 1 is 1.
2. To solve this we will be using bitwise operators > > (left shift) and < < (right shift). Lets say m is 1110, if we do m > > it will return 111 and if we do m < < it will return 110.
3. Create a variable (shiftCounter) which will maintain the number of shifts.
4. In a while loop, we will check if m is less than n. We need to left shift m and n, increment 'shiftCounter'. There will be a situation when m will become equal to n
5. After this we will right shift n (or m) for 'shiftCounter' and return n (or m).

e.g: lets say m is 9 and n is 12. Binary of 9 is 000001001 and 12 is 00001100. shiftCounter=0
1). m is less than n, left shift both m and n. m=00000100 (i.e 4) and n=0000110 (i.e 6), shiftCounter=1
2). Since m is less than n, left shift both m and n. m=0000010 (i.e 2) and n=000011 (i.e 3), shiftCounter=2
3).  Again m is less than n, left shift both m and n. m=000001 (i.e 1) and n=00001 (i.e 1), shiftCounter=3.
4). While loop will end, because now m and n are equal.
5). We will now right shift n (or m) 3 times (because shiftCounter=3), this will give us n=00001000 (i.e 8). So the answer will be 8.

GIT URL: Java Solution of Leet Code's Bitwise AND of Numbers Range problem
Java Solution


-K Himaanshu Shuklaa

No comments:

Post a Comment