Number of Digit One Solutions in C++

// Source : https://leetcode.com/problems/number-of-digit-one/
// Author : Hao Chen
// Date   : 2015-07-17



/*
 *  The idea is:
 *  
 *  1) seprate the n to two parts. considering n is `abc` 
 *     
 *  2) at first, we seprate it to `ab` & `c`, then, 
 *     c == 0,  the # of `1` appears in uints is  "ab * 1"
 *     c == 1,  the # of `1` appears in units is  "ab * 1 + 0 + 1" (0 means the number after `c`)
 *     c > 1 ,  the # of `1` appears in units is  "(ab+1)*1"
 *  
 *  3) at second, we seprate it to `a` & `bc`, then,
 *     b == 0,  the # of `1` appears in tens is  "a * 10"
 *     b == 1,  the # of `1` appears in tens is  "a * 10 + c + 1" (`c` means the number after `b`)
 *     b > 1 ,  the # of `1` appears in tens is  "(a+1)*10"
 *  
 *  4) at thrid, we seprate it to `` & `abc`, then,
 *     a == 0,  the # of `1` appears in tens is  "0 * 100" ( 0 menas the number before `a`)
 *     a == 1,  the # of `1` appears in tens is  "0 * 100 + bc + 1" (`bc` means the number after `a`)
 *     a > 1 ,  the # of `1` appears in tens is  "(0+1)*100" 
 *  
 *  
 *  For some examples: 
 *  0) n = 5,   we have (0+1)*1 = 1 digit 1
 *  1) n = 53,  we have  (5+1)*1  + (0+1)*10   = 16  digit 1
 *  2) n = 20,  we have     (2*1) + (0+1)*10   = 12  digit 1 
 *  3) n = 21,  we have (2*1+0+1) + (0+1)*10   = 13  digit 1
 *  4) n = 13,  we have   (1+1)*1 + (0*10+3+1) = 6   digit 1
 *  5) n = 109, we have  (10+1)*1 + (1*10) + (0*100 + 09 + 1) = 31 digit 1 
 *  
 *  Converting the ideas to code as below:
 *  
 */

class Solution {
public:

    int countDigitOne(int n) {
        long long base=1, left=n, right=0, currDigit=0;
        int numOfOne = 0;
        while(left>0) {
            currDigit = left % 10;
            left = left/ 10;
            
            if (currDigit == 0) {
                numOfOne += (left * base);
            }else if (currDigit == 1) {
                numOfOne += (left * base + right + 1);
            }else {
                numOfOne += ((left+1)*base);
            }
            
            right = right + currDigit * base;
            base *= 10;
        }
        return numOfOne;
    }
};

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


/// Digit DP
/// Time Complexity: O(logn)
/// Space Complexity: O(logn)
class Solution {
public:
    int countDigitOne(int n) {

        if(!n) return 0;

        vector<int> digits = get_digits(n);
        vector<vector<int>> dp(digits.size(), vector<int>(2, -1));
        return dfs(0, 1, digits, dp);
    }

private:
    int dfs(int index, int limit,
            const vector<int>& digits, vector<vector<int>>& dp){

        if(index == digits.size()) return 0;
        if(dp[index][limit] != -1) return dp[index][limit];

        int bound = limit ? digits[index] : 9;
        int res = 0;
        for(int i = 0; i <= bound; i ++){
            res += dfs(index + 1, limit && i == bound, digits, dp);
            if(i == 1) res += i == bound ? get_num(digits, index + 1) + 1 : pow(10, digits.size() - index - 1);
        }
        return dp[index][limit] = res;
    }

    int get_num(const vector<int>& digits, int start){
        int res = 0;
        for(int i = start; i < digits.size(); i ++)
            res = res * 10 + digits[i];
        return res;
    }

    vector<int> get_digits(int x){
        vector<int> res;
        while(x) res.push_back(x % 10), x /= 10;
        reverse(res.begin(), res.end());
        return res;
    }
};


int main() {

    cout << Solution().countDigitOne(13) << endl;
    // 6

    cout << Solution().countDigitOne(100) << endl;
    // 21

    return 0;
}