leetcode - dp - 902. Numbers At Most N Given Digit Set

902. Numbers At Most N Given Digit Set

1. Given an character set D, which contains only digits '1'-'9' in sorted order
2. Given an integer N
3. Count number of integers consisting of D, less than or equal to N

Better code:

https://leetcode.com/problems/numbers-at-most-n-given-digit-set/discuss/168439/C%2B%2B-O(logN)-Clear-code-with-explanation

CY, first attempt

int solve(const vector<int>& nums, const vector<int>& digs,
          int exp10, const vector<int>& power10s) {
  const int n = digs.size();
  int ans = 0;

  for (int i = exp10; i >= 0; --i) {
    int idx = 0;
    for (; idx < n; ++idx)
      if (digs[idx] > nums[i])
        break;

    if (!idx)
      break;

    int cnt = power10s[i];
    if (digs[idx - 1] == nums[i] && i > 0)
      ans += (idx - 1) * cnt;
    else {
      ans += idx * cnt;
      break;
    }
  }
  return ans;
}

int atMostNGivenDigitSet(vector<string>& D, int N) {
  // 2123: 0 ~ 999 + 1000 ~ 1999 + 2000 ~ 2123
  // {1, 2, 3, 4}
  
  // 2567: 0 ~ 999 + 1000 ~ 1999 + 2000 ~ 2567
  int exp10 = 0;
  int64_t power10;
  for (power10 = 10; power10 <= N; power10 *= 10)
    ++exp10;
  
  const int n = D.size();
  
  int ans = 0;

  vector<int> digs;
  digs.reserve(n);
  for (const auto &d : D)
    digs.push_back(stoi(d));

  vector<int> nums;
  nums.reserve(exp10 + 1);
  int NN = N;
  while (NN != 0) {
    nums.push_back(NN % 10);
    NN /= 10;
  }
  
  vector<int> power10s;
  power10s.reserve(exp10+1);
  int cnt = 1;
  power10s.push_back(1);
  for (int j = 0; j < exp10; ++j) {
    cnt *= n;
    ans += cnt;
    power10s.push_back(cnt);
  }
  
  if (nums[exp10] < digs[0])
    return ans;

  return ans + solve(nums, digs, exp10, power10s);
}