Numbers At Most N Given Digit Set Solutions in C++

/// Source : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

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

using namespace std;


/// Recursion, lots of details need to be deal with in this version of code :-(
/// Time Complexity: (logN)
/// Space Complexity: O(logN)
class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {

        string dset = "";
        for(string d: D)
            dset += d;

        int res = 0;
        int dnum = to_string(N).size();
        for(int i = 1; i < dnum; i ++)
            res += (int)pow(dset.size(), i);

        return res + atMostNGivenDigitSet(dset, N, dnum);
    }

private:
    int atMostNGivenDigitSet(const string& dset, int N, int d){

        int dnum = to_string(N).size();
        if(dnum < d)
            return 0;
        if(dnum == 1){
            int res = 0;
            for(char c: dset)
                if(c - '0' <= N)
                    res ++;
            return res;
        }

        int res = 0;
        char leftmost = to_string(N)[0];
        for(int i = 0; i < dset.size(); i ++)
            if(dset[i] < leftmost)
                res += (int)pow(dset.size(), dnum - 1);
            else if(dset[i] == leftmost)
                res += atMostNGivenDigitSet(dset, N - (leftmost - '0') * pow(10, dnum - 1), dnum - 1);
            else
                break;

        return res;
    }
};


int main() {

    vector<string> D1 = {"1","3","5","7"};
    cout << Solution().atMostNGivenDigitSet(D1, 100) << endl;
    // 20

    vector<string> D2 = {"1", "4", "9"};
    cout << Solution().atMostNGivenDigitSet(D2, 1000000000) << endl;
    // 29523

    vector<string> D3 = {"3", "4", "8"};
    cout << Solution().atMostNGivenDigitSet(D3, 4) << endl;
    // 2

    vector<string> D4 = {"1", "2", "3", "6", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D4, 211) << endl;
    // 79

    vector<string> D5 = {"1", "5", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D5, 10212) << endl;
    // 340

    return 0;
}

/// Source : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
/// Author : liuyubobobo
/// Time   : 2018-09-11

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

using namespace std;


/// Recursion
/// Second version of codes, more clear :-)
///
/// Time Complexity: (logN)
/// Space Complexity: O(logN)
class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {

        string dset = "";
        for(string d: D)
            dset += d;

        int res = 0;
        int dnum = to_string(N).size();
        for(int i = 1; i < dnum; i ++)
            res += (int)pow(dset.size(), i);

        return res + atMostNGivenDigitSet(dset, to_string(N));
    }

private:
    int atMostNGivenDigitSet(const string& dset, const string& snum){

        int dnum = snum.size();
        if(snum.size() == 0)
            return 1;

        int res = 0;
        for(int i = 0; i < dset.size(); i ++)
            if(dset[i] < snum[0])
                res += (int)pow(dset.size(), snum.size() - 1);
            else if(dset[i] == snum[0])
                res += atMostNGivenDigitSet(dset, snum.substr(1));
            else
                break;

        return res;
    }
};


int main() {

    vector<string> D1 = {"1","3","5","7"};
    cout << Solution().atMostNGivenDigitSet(D1, 100) << endl;
    // 20

    vector<string> D2 = {"1", "4", "9"};
    cout << Solution().atMostNGivenDigitSet(D2, 1000000000) << endl;
    // 29523

    vector<string> D3 = {"3", "4", "8"};
    cout << Solution().atMostNGivenDigitSet(D3, 4) << endl;
    // 2

    vector<string> D4 = {"1", "2", "3", "6", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D4, 211) << endl;
    // 79

    vector<string> D5 = {"1", "5", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D5, 10212) << endl;
    // 340

    return 0;
}

/// Source : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
/// Author : liuyubobobo
/// Time   : 2018-09-11

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

using namespace std;


/// Memorization
/// Time Complexity: (logN)
/// Space Complexity: O(logN)
class Solution {

public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {

        string dset = "";
        for(string d: D)
            dset += d;

        int res = 0;
        int dnum = to_string(N).size();
        for(int i = 1; i < dnum; i ++)
            res += (int)pow(dset.size(), i);

        // dp[i]: the number of num <= last i digits of N
        vector<int> dp(dnum + 1, -1);
        return res + atMostNGivenDigitSet(dset, to_string(N), dp);
    }

private:
    int atMostNGivenDigitSet(const string& dset, const string& snum,
                             vector<int>& dp){

        if(snum.size() == 0)
            return 1;

        if(dp[snum.size()] != -1)
            return dp[snum.size()];

        int res = 0;
        for(int i = 0; i < dset.size(); i ++)
            if(dset[i] < snum[0])
                res += (int)pow(dset.size(), snum.size() - 1);
            else if(dset[i] == snum[0])
                res += atMostNGivenDigitSet(dset, snum.substr(1), dp);
            else
                break;

        return dp[snum.size()] = res;
    }
};


int main() {

    vector<string> D1 = {"1","3","5","7"};
    cout << Solution().atMostNGivenDigitSet(D1, 100) << endl;
    // 20

    vector<string> D2 = {"1", "4", "9"};
    cout << Solution().atMostNGivenDigitSet(D2, 1000000000) << endl;
    // 29523

    vector<string> D3 = {"3", "4", "8"};
    cout << Solution().atMostNGivenDigitSet(D3, 4) << endl;
    // 2

    vector<string> D4 = {"1", "2", "3", "6", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D4, 211) << endl;
    // 79

    vector<string> D5 = {"1", "5", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D5, 10212) << endl;
    // 340

    return 0;
}

/// Source : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
/// Author : liuyubobobo
/// Time   : 2018-09-11

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

using namespace std;


/// Dynamic Programming
/// Time Complexity: (logN)
/// Space Complexity: O(logN)
class Solution {

public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {

        string dset = "";
        for(string d: D)
            dset += d;

        string snum = to_string(N);
        int dnum = snum.size();

        // dp[i]: the number of num <= last i digits of N
        vector<int> dp(dnum + 1, 0);
        dp[0] = 1;
        for(int i = 1; i <= dnum; i ++){
            for(int j = 0; j < dset.size(); j ++)
                if(dset[j] < snum[dnum - i])
                    dp[i] += (int)pow(dset.size(), i - 1);
                else if(dset[j] == snum[dnum - i])
                    dp[i] += dp[i - 1];
                else
                    break;
        }

        int res = 0;
        for(int i = 1; i < dnum; i ++)
            res += (int)pow(dset.size(), i);
        return res + dp[dnum];
    }
};


int main() {

    vector<string> D1 = {"1","3","5","7"};
    cout << Solution().atMostNGivenDigitSet(D1, 100) << endl;
    // 20

    vector<string> D2 = {"1", "4", "9"};
    cout << Solution().atMostNGivenDigitSet(D2, 1000000000) << endl;
    // 29523

    vector<string> D3 = {"3", "4", "8"};
    cout << Solution().atMostNGivenDigitSet(D3, 4) << endl;
    // 2

    vector<string> D4 = {"1", "2", "3", "6", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D4, 211) << endl;
    // 79

    vector<string> D5 = {"1", "5", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D5, 10212) << endl;
    // 340

    return 0;
}

/// Source : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
/// Author : liuyubobobo
/// Time   : 2018-09-11

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Mathematics
/// map digits of D into {0, 1, 2, ...}
/// if there're d digits in D, then it's a d-based number problem
///
/// Time Complexity: (logN)
/// Space Complexity: O(logN)
class Solution {

public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {

        string dset = "";
        for(string d: D)
            dset += d;

        unordered_map<char, int> dmap;
        for(int i = 0; i < dset.size(); i ++)
            dmap[dset[i]] = i + 1;

        string snum = to_string(N);
        for(int i = 0; i < snum.size(); i ++){
            int j;
            for(j = 0; j <= dset.size(); j ++)
                if(j == dset.size() || dset[j] > snum[i]){
                    int k;
                    snum[i] = dset[j - 1];
                    for(k = i; k >= 0 && snum[k] == '0'; k--);
                    if(k >= 0) snum[k] = dmap[snum[k]] - 1 >= 0 ? dset[dmap[snum[k]] - 1] : '0';
                    for(k = k + 1; k < snum.size(); k ++)
                        snum[k] = dset.back();
                    break;
                }
                else if(dset[j] == snum[i])
                    break;
        }

//        cout << "sum:" << snum << endl;
        int res = 0;
        for(char c: snum)
            res = res * dset.size() + dmap[c];
        return res;
    }
};


int main() {

    vector<string> D1 = {"1","3","5","7"};
    cout << Solution().atMostNGivenDigitSet(D1, 100) << endl;
    // 20

    vector<string> D2 = {"1", "4", "9"};
    cout << Solution().atMostNGivenDigitSet(D2, 1000000000) << endl;
    // 29523

    vector<string> D3 = {"3", "4", "8"};
    cout << Solution().atMostNGivenDigitSet(D3, 4) << endl;
    // 2

    vector<string> D4 = {"1", "2", "3", "6", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D4, 211) << endl;
    // 79

    vector<string> D5 = {"1", "5", "7", "8"};
    cout << Solution().atMostNGivenDigitSet(D5, 10212) << endl;
    // 340

    vector<string> D6 = {"7"};
    cout << Solution().atMostNGivenDigitSet(D6, 8) << endl;
    // 1

    vector<string> D7 = {"1", "7"};
    cout << Solution().atMostNGivenDigitSet(D7, 231) << endl;
    // 10

    vector<string> D8 = {"1", "6", "7", "8", "9"};
    cout << Solution().atMostNGivenDigitSet(D8, 433) << endl;
    // 55

    vector<string> D9 = {"5"};
    cout << Solution().atMostNGivenDigitSet(D9, 6122) << endl;
    // 4

    return 0;
}