C++ Divide-and-conquer
I guess no one want to read this long solution. So I am lazy to add comment\n```\nclass Solution {\npublic:\n   int numDupDigitsAtMostN(int N) {\n      vector v
I guess no one want to read this long solution. So I am lazy to add comment\n```\nclass Solution {\npublic:\n   int numDupDigitsAtMostN(int N) {\n      vector<int> v = toVec(N);\n      int n1 = numNoRepeat1(v, {}, 0);\n      int n2 = numNoRepeat2(v.size() - 1);\n      cout << N << " " << n1 << " " << n2 << endl;\n      return N - n1 - n2;\n   }\n\n   // from 10^pow to N \n   int numNoRepeat1(vector<int> & v, set<int> used, int i) {\n      if (i == v.size()) return 1;\n      int res = 0;\n      int nCanbeUse = v[i];  // 0,1,2,3,4,...v[0]-1\n      if (i == 0) nCanbeUse--; //leading digit cannot be 0\n      for (auto x : used) if (x < v[i]) nCanbeUse--;\n      res += nCanbeUse * permutation(10 - used.size() - 1, v.size() - i - 1);\n\n      //repeated, early return\n      if(used.count(v[i])) return res;\n\n      used.insert(v[i]);\n      res += numNoRepeat1(v, used, i + 1);\n      return res;\n   }\n\n   int permutation(int num, int k) {\n      int prod = 1;\n      while (k--) prod *= num--;\n      return prod;\n   }\n\n   // from 0 to 10^pow10 \n   int numNoRepeat2(int pow10) {\n      int sum = 0;\n      while (pow10) {\n         sum += 9 * permutation(9, pow10 - 1);\n         pow10--;\n      }\n      return sum;\n   }\n\n   vector<int> toVec(int N) {\n      auto s = to_string(N);\n      vector<int> v;\n      for (auto c : s) v.push_back(c - \'0\');\n      return v;\n   }\n};
[]