Numbers At Most N Given Digit Set — Problem & Solution
Numbers At Most N Given Digit Set solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Numbers At Most N Given Digit Set is a hard coding problem on dynamic programming, math and Digit DP, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Digit DP
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
digits is a list of distinct single-digit strings from "1" to "9", sorted in increasing order. You may write numbers using these digits only, each digit as many times as you like — with digits = ["1","3","5"] you can write 13, 551 or 1351315.
Return how many positive integers you can write that are less than or equal to n.
Example 1
Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: The 4 one-digit numbers and the 16 two-digit numbers 11, 13, …, 77 are all at most 100.
Example 2
Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation: 3 + 9 + 27 + … + 3^9 numbers of one to nine digits; no ten-digit number made of these digits is at most 10^9.
Example 3
Input: digits = ["7"], n = 8
Output: 1
Constraints
1 <= digits.length <= 9digits[i].length == 1digits[i] is a digit from '1' to '9'All values in digits are unique and sorted in increasing order1 <= n <= 10^9
Hints for Numbers At Most N Given Digit Set
Hint 1
Let
nhaveKdigits and letDbe the size of the digit set. How many usable numbers have fewer thanKdigits?Hint 2
All of them:
D + D^2 + … + D^(K-1). The remaining work is the numbers with exactlyKdigits.Hint 3
Walk along
nfrom its first digit. At positioni, every allowed digit smaller thann[i]frees up the remaining positions (D^(K-1-i)choices). Ifn[i]itself is allowed, continue to the next position; otherwise stop. Reaching the end meansnitself counts.
How to solve Numbers At Most N Given Digit Set
Count numbers shorter than n with a geometric sum, then count K-digit numbers ≤ n digit by digit, the classic digit-DP walk along the tight prefix.
Approach
- Let
sbe the decimal string ofn,K = len(s)andD = len(digits). - Add
D^lenfor every length from 1 to K−1. - For each position
iofs: add(number of digits < s[i]) * D^(K-1-i). Ifs[i]is not in the set, return the total now. - If the loop finishes,
nitself is writable: return the total plus 1.
Why it works
A K-digit candidate is below n exactly when it agrees with n on some prefix and then has a smaller digit; the position of the first disagreement partitions those candidates, and once a smaller digit is placed the remaining positions are free, giving D^(K-1-i) each. The walk can only continue past position i if the candidate copies s[i], which needs s[i] in the set. Numbers with fewer digits are always smaller than n, and none have leading zeros because the set has no 0.
Complexity
- Time —
O(K · D) with K ≤ 10 - Space —
O(K)
Pitfalls
- Forgetting the final +1 for
nitself when every digit ofnis available. - Stopping too late: when
s[i]is missing, the numbers counted so far are complete — do not keep adding. - Computing
D^Kin 32-bit (9^10 overflows); only powers up toD^(K-1)are needed.
Reference solution
Python
from typing import List
def atMostNGivenDigitSet(digits: List[str], n: int) -> int:
s = str(n)
k = len(s)
d = len(digits)
total = sum(d ** length for length in range(1, k))
for i, ch in enumerate(s):
smaller = sum(1 for x in digits if x < ch)
total += smaller * d ** (k - 1 - i)
if ch not in digits:
return total
return total + 1Java
public static int atMostNGivenDigitSet(String[] digits, int n) {
String s = String.valueOf(n);
int k = s.length(), d = digits.length;
long[] pw = new long[k];
pw[0] = 1;
for (int i = 1; i < k; i++) pw[i] = pw[i - 1] * d;
long total = 0;
for (int len = 1; len < k; len++) total += pw[len];
for (int i = 0; i < k; i++) {
char c = s.charAt(i);
int smaller = 0;
boolean same = false;
for (String dg : digits) {
if (dg.charAt(0) < c) smaller++;
else if (dg.charAt(0) == c) same = true;
}
total += smaller * pw[k - 1 - i];
if (!same) return (int) total;
}
return (int) (total + 1);
}C++
int atMostNGivenDigitSet(vector<string>& digits, int n) {
string s = to_string(n);
int k = s.size(), d = digits.size();
vector<long long> pw(k, 1);
for (int i = 1; i < k; i++) pw[i] = pw[i - 1] * d;
long long total = 0;
for (int len = 1; len < k; len++) total += pw[len];
for (int i = 0; i < k; i++) {
int smaller = 0;
bool same = false;
for (const string& dg : digits) {
if (dg[0] < s[i]) smaller++;
else if (dg[0] == s[i]) same = true;
}
total += smaller * pw[k - 1 - i];
if (!same) return (int)total;
}
return (int)(total + 1);
}JavaScript
var atMostNGivenDigitSet = function(digits, n) {
var s = String(n);
var k = s.length, d = digits.length;
var pw = [1];
for (var i = 1; i < k; i++) pw.push(pw[i - 1] * d);
var total = 0;
for (var len = 1; len < k; len++) total += pw[len];
for (var i = 0; i < k; i++) {
var smaller = 0, same = false;
for (var j = 0; j < d; j++) {
if (digits[j] < s[i]) smaller++;
else if (digits[j] === s[i]) same = true;
}
total += smaller * pw[k - 1 - i];
if (!same) return total;
}
return total + 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming