Numbers At Most N Given Digit Set - Practice Coding Problems

Numbers At Most N Given Digit Set - Problem

Array Math String Binary Search Dynamic Programming Hard

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want.

For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Input & Output

Example 1 — Basic Case

$ Input: digits = ["1","3","5"], n = 100

› Output: 20

💡 Note: 1-digit: 1,3,5 (count=3). 2-digit: 11,13,15,31,33,35,51,53,55 (count=9). 3-digit: 111,113,115,131,133,135,151,153,155 (count=8). Total = 3+9+8 = 20

Example 2 — Single Digit

$ Input: digits = ["1","4","9"], n = 1000000000

› Output: 29523

💡 Note: Count systematically: 1-digit (3), 2-digit (9), 3-digit (27), ..., up to 9-digit numbers, plus valid 10-digit numbers ≤ 1000000000

Example 3 — Small Target

$ Input: digits = ["7"], n = 8

› Output: 1

💡 Note: Only digit 7 available. Only valid number ≤ 8 is 7 itself. Count = 1

Constraints

1 ≤ digits.length ≤ 9
digits[i].length == 1
digits[i] is a digit from '1' to '9'
All the values in digits are unique
digits is sorted in non-decreasing order
1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

digits=['1','3','5'], n=100

Count by Length

1-digit: 3 numbers, 2-digit: 9 numbers, 3-digit: check constraints

Output

Total count = 20

Key Takeaway

🎯 Key Insight: Count by length groups first, then handle same-length numbers with digit-by-digit constraints

Asked in

G Google 15 F Facebook 12 A Amazon 8

The key insight is to count valid numbers mathematically without generating them. First count all numbers with fewer digits (using powers), then handle same-length numbers by comparing digit-by-digit. Best approach uses mathematical counting with Time: O(k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Generation	O(d^k)	O(d^k)	Generate all possible numbers and count valid ones
Mathematical Counting	O(k)	O(1)	Count valid numbers mathematically without generating them
Recursive with Memoization	O(k × d)	O(k × d)	Use recursion with caching to avoid recomputing subproblems

Brute Force Generation — Algorithm Steps

Generate all 1-digit numbers from digits
Generate all 2-digit numbers from digits
Continue until numbers exceed n
Count all valid numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate 1-digit

Create all single digit numbers

Generate 2-digit

Create all two digit combinations

Filter Valid

Count numbers ≤ n

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int count = 0;

void generateNumbers(char digits[][2], int numDigits, int length, char* current, int pos, int n) {
    if (pos == length) {
        int num = atoi(current);
        if (num <= n && num > 0) {
            count++;
        }
        return;
    }
    
    for (int i = 0; i < numDigits; i++) {
        current[pos] = digits[i][0];
        current[pos + 1] = '\0';
        generateNumbers(digits, numDigits, length, current, pos + 1, n);
    }
}

int solution(char digits[][2], int numDigits, int n) {
    count = 0;
    char nStr[20];
    sprintf(nStr, "%d", n);
    int nLen = strlen(nStr);
    
    char current[20];
    
    // Generate numbers of all lengths from 1 to len(n)
    for (int length = 1; length <= nLen; length++) {
        generateNumbers(digits, numDigits, length, current, 0, n);
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse digits (simplified parsing)
    char digits[10][2];
    int numDigits = 0;
    
    // Simple parsing for ["1","3","5"] format
    char* ptr = line;
    while (*ptr) {
        if (*ptr >= '0' && *ptr <= '9') {
            digits[numDigits][0] = *ptr;
            digits[numDigits][1] = '\0';
            numDigits++;
        }
        ptr++;
    }
    
    int n;
    scanf("%d", &n);
    
    printf("%d\n", solution(digits, numDigits, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d^k)

Where d is number of digits and k is number of digits in n - generates all possible combinations

✓ Linear Growth

Space Complexity

O(d^k)

Stores all generated numbers in memory

✓ Linear Space

28.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler