Numbers At Most N Given Digit Set

HardMathdigit dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a sorted array digits of distinct single-character strings, each one of '1' to '9'. You can build positive integers by writing digits from this set, reusing any digit as many times as you like (for example, ["1","3"] builds 1, 13, 311, ...). Return how many positive integers you can build that are **less than or equal to** n. n can be as large as 10^9, so count by digit positions instead of generating numbers.

Examples

Input: digits = ["1","3","5","7"], n = 100
Output: 20
4 one-digit numbers and 16 two-digit numbers; no three-digit number built from these digits is <= 100.
Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Numbers with 1 to 9 digits: 3 + 9 + ... + 3^9 = 29523. Every 10-digit option exceeds 10^9.
Input: digits = ["7"], n = 8
Output: 1
Only 7 qualifies.

Constraints

  • 1 <= digits.length <= 9
  • digits[i].length == 1 and digits[i] is one of "1" to "9"
  • All values in digits are distinct and sorted ascending
  • 1 <= n <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More digit dp problems