## Numbers At Most N Given Digit Set

• 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
``````