Numbers At Most N Given Digit Set

Hard
1283.

Numbers At Most N Given Digit Set

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.

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 <= 9
  • digits[i].length == 1
  • digits[i] is a digit from '1' to '9'
  • All values in digits are unique and sorted in increasing order
  • 1 <= n <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} digits
 * @param {number} n
 * @return {number}
 */
var atMostNGivenDigitSet = function(digits, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 9
  • digits[i].length == 1
  • digits[i] is a digit from '1' to '9'
  • All values in digits are unique and sorted in increasing order
  • 1 <= n <= 10^9

Hints for Numbers At Most N Given Digit Set

  1. Hint 1

    Let n have K digits and let D be the size of the digit set. How many usable numbers have fewer than K digits?

  2. Hint 2

    All of them: D + D^2 + … + D^(K-1). The remaining work is the numbers with exactly K digits.

  3. Hint 3

    Walk along n from its first digit. At position i, every allowed digit smaller than n[i] frees up the remaining positions (D^(K-1-i) choices). If n[i] itself is allowed, continue to the next position; otherwise stop. Reaching the end means n itself 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

  1. Let s be the decimal string of n, K = len(s) and D = len(digits).
  2. Add D^len for every length from 1 to K−1.
  3. For each position i of s: add (number of digits < s[i]) * D^(K-1-i). If s[i] is not in the set, return the total now.
  4. If the loop finishes, n itself 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 n itself when every digit of n is available.
  • Stopping too late: when s[i] is missing, the numbers counted so far are complete — do not keep adding.
  • Computing D^K in 32-bit (9^10 overflows); only powers up to D^(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 + 1

Java

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