# LeetCode : 0338. Counting Bits (bits)
###### tags:`leetcode`

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class Solution01 {
public:
    vector<int> countBits(int n) {
        if(n==0) return {0};
        vector<int> dp(n+1, 0); //n=3 = 4 size = {0,0,0,0}
        //vector<int>dp {0}; //set dp 0
        dp[1]=1;
        for(int i=2;i<=n;i++){
            printf("i=%d\n",i);
            if(i%2==0){
                //printf("%2=0\n");
                dp[i] = dp[i/2];    
            }
            else{
                dp[i] = dp[i-1] + 1;
            }
            //printf("%d\n",dp[i]);
        }
        return dp;
    }
};

//run step
//0  = >   0000 dp[0]  {0}
//1  = >   0001 dp[1]  {0,1}
//2  = >   0010 dp[2]  {0,1,1}                  >> %2=0 >> dp[2] >> dp[2/2] => dp[1] >> 1
//3  = >   0011 dp[3]  {0,1,2}                  >> %2=1 >> dp[3] >> dp[i-1] +1 >> dp[3-1] >> dp[2]+1 >> 1 + 1 >> 2
//4  = >   0100 dp[4]  {0,1,2,1}                >> %2=0 >> dp[4] >> dp[4/2] >> dp[2] >>  1
//5  = >   0101 dp[5]  {0,1,2,1,2}              >> %2=1 >> dp[5] >> dp[i-1] +1 >> dp[5-1] >> dp[4]+1 >> 1 + 1 >> 2
//6  = >   0110 dp[6]  {0,1,2,1,2,2}            >> %2=0 >> dp[6] >> dp[6/2] >> dp[3] >>  2
//7  = >   0111 dp[7]  {0,1,2,1,2,2,3}          >> %2=1 >> dp[7] >> dp[i-1] +1 >> dp[7-1] >> dp[6]+1 >> 2 + 1 >> 3
//8  = >   1000 dp[8]  {0,1,2,1,2,2,3,1}        >> %2=0 >> dp[8] >> dp[8/2] >> dp[4] >>  1
//9  = >   1001 dp[9]  {0,1,2,1,2,2,3,1,2}
//10 = >   1010 dp[10] {0,1,2,1,2,2,3,1,2,2}
//11 = >   1011 dp[11] {0,1,2,1,2,2,3,1,2,2,3}
//12 = >   1010 dp[12] {0,1,2,1,2,2,3,1,2,2,3,2}
//13 = >   1101 dp[13] {0,1,2,1,2,2,3,1,2,2,3,2,3}
//14 = >   1110 dp[14] {0,1,2,1,2,2,3,1,2,2,3,2,3,3}
//15 = >   1111 dp[15] {0,1,2,1,2,2,3,1,2,2,3,2,3,3,4}
//16 = >0010000 dp[16] {0,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1}
//32 = >0100000 dp[32]
//64 = >1000000 dp[64]


int main(void)
{
    BaseVectorPrint printVector;
    Solution01 runfunc;

    vector<int> test01 = {  4,  5,  1,  8,  2 };
    vector<int> test02 = {  1,  2,  3,  4 };
    vector<int> test03 = { -1,  1,  0, -3,  3 };
    vector<int> ans ;
    int testint = 15;

    ans = runfunc.countBits(testint);
    printVector.BasePrint02(ans);

    //printf("%d\n",input_Nums);
    printf("test\n");
    system("pause");
}

> //tip consider point odd and even rule