09/13

surajr · surajr · commit 885b9f09d089 · 2017-09-13T04:37:37.000-07:00
diff --git a/README.md b/README.md
@@ -25,6 +25,7 @@ Feel free to add issues, comment and pull request.
 |---------------- |---------------- | ----------- | --------------- | --------------- | ------------- |-----|
 | Careercup  | [Permutation Casewise](https://www.careercup.com/question?id=6255535581036544) | [Java](./java/PermuteCasewise.java) \| [Python](./Python/) | _O(2^n)_       | _O(1)_          |  Medium       |         |
 | Leetcode  | [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/description/) | [Java](./java/hammingDistance.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Easy       |         |
+| Leetcode  | [338. Counting Bits](https://leetcode.com/problems/counting-bits/description/) | [Java](./java/countBits.java) \| [Python](./Python/) | _O(nk)_       | _O(n)_          |  Medium       |         |
 
 
 ## Arrays
@@ -86,6 +87,7 @@ Feel free to add issues, comment and pull request.
 | Website 		| Title           |  Solution    |  Time           | Space           | Difficulty    |  Note| 
 |---------------- |---------------- | ----------- | --------------- | --------------- | ------------- |-----|
 | Leetcode  | [654. Maximum Binary Tree](https://leetcode.com/contest/leetcode-weekly-contest-44/problems/maximum-binary-tree/) | [Java](./java/ConstructMaximumBinaryTree.java) \| [Python](./Python/) | _O(n log n)_       | _O(n)_          |  Easy       |         |
+| Leetcode  | [50. Pow(x, n)](https://leetcode.com/problems/powx-n/description/) | [Java](./java/myPow.java) \| [Python](./Python/) | _O()_       | _O(n)_          |  Medium       |         |
 
 
 ## Recursion
diff --git a/java/countBits.java b/java/countBits.java
@@ -0,0 +1,32 @@
+/*
+    The least significant bit which las 1 corresponds to 0 bit in n - 1.
+    
+    AND N and N-1 and keep doing till you hit 0. Count the number of steps and store it in array
+    
+    Time: O(nk) k - number of bits 
+    Space O(1)
+
+*/
+
+class Solution {
+    public int[] countBits(int num) {   
+          
+        int [] result = new int[num+1];
+        
+        for(int i=0; i<=num; i++)
+            result[i]=hammingBits(i);
+        return result;
+        
+    }
+    
+    public int hammingBits(int n)
+    {
+        int sum = 0;
+        while(n !=0)
+        {
+            sum ++;
+            n = n&n-1;
+        }        
+        return sum;
+    }
+}
diff --git a/java/myPow.java b/java/myPow.java
@@ -0,0 +1,15 @@
+class Solution {
+    public double myPow(double x, int n) {
+        
+        if(n==0) return 1;
+        
+        if(n<0)
+        {
+            n = -n;
+            x = 1/x;
+        }
+        
+        return n%2 == 0? myPow(x*x, n/2): x*myPow(x*x, n/2);
+        
+    }
+}
