Skip to content

902. Numbers At Most N Given Digit Set 👍

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int atMostNGivenDigitSet(vector<string>& digits, int n) {
    int ans = 0;
    const string num = to_string(n);

    for (int i = 1; i < num.length(); ++i)
      ans += pow(digits.size(), i);

    for (int i = 0; i < num.length(); ++i) {
      bool dHasSameNum = false;
      for (const string& digit : digits) {
        if (digit[0] < num[i])
          ans += pow(digits.size(), num.length() - i - 1);
        else if (digit[0] == num[i])
          dHasSameNum = true;
      }
      if (!dHasSameNum)
        return ans;
    }

    return ans + 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int atMostNGivenDigitSet(String[] digits, int n) {
    int ans = 0;
    final String num = String.valueOf(n);

    for (int i = 1; i < num.length(); ++i)
      ans += (int) Math.pow(digits.length, i);

    for (int i = 0; i < num.length(); ++i) {
      boolean dHasSameNum = false;
      for (final String digit : digits) {
        if (digit.charAt(0) < num.charAt(i))
          ans += (int) Math.pow(digits.length, num.length() - i - 1);
        else if (digit.charAt(0) == num.charAt(i))
          dHasSameNum = true;
      }
      if (!dHasSameNum)
        return ans;
    }

    return ans + 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
    ans = 0
    num = str(n)

    for i in range(1, len(num)):
      ans += pow(len(digits), i)

    for i, c in enumerate(num):
      dHasSameNum = False
      for digit in digits:
        if digit[0] < c:
          ans += pow(len(digits), len(num) - i - 1)
        elif digit[0] == c:
          dHasSameNum = True
      if not dHasSameNum:
        return ans

    return ans + 1