Leetcode

Numbers At Most N Given Digit Set

May 26, 2022 by aAshish

  • Time:O(\log n)
  • Space:O(\log n)

C++

 
class Solution {
 public:
  int atMostNGivenDigitSet(vector<string>& D, int N) {
    int ans = 0;
    string num = to_string(N);

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

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

    return ans + 1;
  }
};

JAVA

 
class Solution {
  public int atMostNGivenDigitSet(String[] D, int N) {
    int ans = 0;
    String num = String.valueOf(N);

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

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

    return ans + 1;
  }
}

Python

 
class Solution:
  def atMostNGivenDigitSet(self, D: List[str], N: int) -> int:
    ans = 0
    num = str(N)

    for i in range(1, len(num)):
      ans += len(D)**i

    for i, c in enumerate(num):
      dHasSameNum = False
      for digit in D:
        if digit < c:
          ans += len(D)**(len(num) - i - 1)
        elif digit == c:
          dHasSameNum = True
      if not dHasSameNum:
        return ans

    return ans + 1