solve 338: counting bits

andavid · andavid · commit ba70f3cf3f26 · 2019-04-14T23:18:41.000+08:00
diff --git a/vscode/338.counting-bits.java b/vscode/338.counting-bits.java
@@ -0,0 +1,51 @@
+/*
+ * @lc app=leetcode id=338 lang=java
+ *
+ * [338] Counting Bits
+ *
+ * https://leetcode.com/problems/counting-bits/description/
+ *
+ * algorithms
+ * Medium (63.91%)
+ * Total Accepted:    151.8K
+ * Total Submissions: 237.5K
+ * Testcase Example:  '2'
+ *
+ * Given a non negative integer number num. For every numbers i in the range 0
+ * ≤ i ≤ num calculate the number of 1's in their binary representation and
+ * return them as an array.
+ * 
+ * Example 1:
+ * 
+ * 
+ * Input: 2
+ * Output: [0,1,1]
+ * 
+ * Example 2:
+ * 
+ * 
+ * Input: 5
+ * Output: [0,1,1,2,1,2]
+ * 
+ * 
+ * Follow up:
+ * 
+ * 
+ * It is very easy to come up with a solution with run time
+ * O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a
+ * single pass?
+ * Space complexity should be O(n).
+ * Can you do it like a boss? Do it without using any builtin function like
+ * __builtin_popcount in c++ or in any other language.
+ * 
+ */
+class Solution {
+  public int[] countBits(int num) {
+    int[] count = new int[num + 1];
+    for (int i = 1; i <= num; i++) {
+      count[i] = count[i & (i-1)] + 1;
+    }
+    return count;
+  }
+}
+
