add 201

fishercoder1534 · fishercoder1534 · commit 10c083b31138 · 2017-05-03T07:33:14.000-07:00
diff --git a/README.md b/README.md
@@ -258,6 +258,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |205|[Isomorphic Strings](https://leetcode.com/problems/isomorphic-strings/)|[Solution](../../blmaster/src/94stevesun/algorithms/IsomorphicStrings.java)| O(n)|O(1) | Easy
 |204|[Count Primes](https://leetcode.com/problems/count-primes/)|[Solution](../master/src/main/java/com/stevesun/solutions/CountPrime.java)| O(?)|O(?) | Easy
 |202|[Happy Number](https://leetcode.com/problems/happy-number/)|[Solution](../master/src/main/java/com/stevesun/solutions/HappyNumber.java)| O(k)|O(k) | Easy
+|201|[Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/)|[Solution](../master/src/main/java/com/stevesun/solutions/_201.java)| O(min(m,n))|O(1) | Medium | Bit Manipulation
 |200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Union Find](../master/src/main/java/com/stevesun/solutions/NumberOfIslandsUnionFind.java) [DFS](../../blmaster/MEDIUM/src/medium/NumberofIslandsDFS.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
 |198|[House Robber](https://leetcode.com/problems/house-robber/)|[Solution](../master/src/main/java/com/stevesun/solutions/HouseRobber.java)| O(n)|O(n)| Easy | DP
 |190|[Reverse Bits](https://leetcode.com/problems/reverse-bits/)|[Solution](../master/src/main/java/com/stevesun/solutions/ReverseBits.java)| O(n)|O(1)| Easy | Bit Manipulation
diff --git a/src/main/java/com/stevesun/solutions/_201.java b/src/main/java/com/stevesun/solutions/_201.java
@@ -0,0 +1,36 @@
+package com.stevesun.solutions;
+
+/**
+ * 201. 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.
+
+ For example, given the range [5, 7], you should return 4.
+
+ */
+public class _201 {
+
+    //this naive approach works, but will result in TLE as expected for 8256/8266 test cases: (0, 2147483647)
+    public int rangeBitwiseAnd_TLE(int m, int n) {
+        if (m == 0) return m;
+        int result = m;
+        for (int i = m+1; i <= n; i++) {
+            result &= i;
+        }
+        return result;
+    }
+
+    //credit: https://discuss.leetcode.com/topic/28538/java-python-easy-solution-with-explanation
+    //Bitwise AND operation within range actually turns out to be doing some operations with just these two boundary numbers: m and n
+    //e.g. 5 and 7, in binary, they are 101 and 111, the result for [5,7] is 5&6&7 which is 101&110&111
+    //this we can understand it to be shifting the digits of m and n from left to right until they become the same, then we pad that number with zeroes on the right side
+    public int rangeBitwiseAnd(int m, int n) {
+        int i = 0;
+        while (m != n) {
+            m >>= 1;
+            n >>= 1;
+            i++;
+        }
+        return (n << i);
+    }
+}
diff --git a/src/test/java/com/stevesun/_201Test.java b/src/test/java/com/stevesun/_201Test.java
@@ -0,0 +1,71 @@
+package com.stevesun;
+
+import com.stevesun.solutions._201;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 5/3/17.
+ */
+public class _201Test {
+    private static _201 test;
+    private static int m;
+    private static int n;
+    private static int actual;
+    private static int expected;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _201();
+    }
+
+    @Test
+    public void test1(){
+        m = 5;
+        n = 7;
+        actual = test.rangeBitwiseAnd_TLE(m, n);
+        expected = 4;
+        assertEquals(expected, actual);
+        actual = test.rangeBitwiseAnd(m, n);
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test2(){
+        m = 1;
+        n = 2;
+        actual = test.rangeBitwiseAnd_TLE(m, n);
+        expected = 0;
+        assertEquals(expected, actual);
+        actual = test.rangeBitwiseAnd(m, n);
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test3(){
+        m = 0;
+        n = 2147483647;
+        long start = System.currentTimeMillis();
+        actual = test.rangeBitwiseAnd_TLE(m, n);
+        System.out.println("It took " + (System.currentTimeMillis() - start) + " ms to finish.");
+        expected = 0;
+        assertEquals(expected, actual);
+        actual = test.rangeBitwiseAnd(m, n);
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test4(){
+        m = 20000;
+        n = 2147483647;
+        long start = System.currentTimeMillis();
+//        actual = test.rangeBitwiseAnd_TLE(m, n);
+        System.out.println("It took " + (System.currentTimeMillis() - start) + " ms to finish.");
+        expected = 0;
+        assertEquals(expected, actual);
+        actual = test.rangeBitwiseAnd(m, n);
+        assertEquals(expected, actual);
+    }
+}
