Update counting-bits.cpp

kamyu104 · kamyu104 · commit 0581a4f8703b · 2016-03-18T00:21:01.000+08:00
diff --git a/C++/counting-bits.cpp b/C++/counting-bits.cpp
@@ -2,6 +2,19 @@
 // Space: O(n)
 
 class Solution {
+public:
+    vector<int> countBits(int num) {
+        vector<int> res{0};
+        for (int i = 1; i <= num; ++i) {
+            res.emplace_back(res[i >> 1] + (i & 1));
+        }
+        return res;
+    }
+};
+
+// Time:  O(n)
+// Space: O(n)
+class Solution2 {
 public:
     vector<int> countBits(int num) {
         vector<int> res{0};
