Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 902 Numbers At Most N Given Digit Set - Problem Statement

LeetCode 902

Given an array of digits (like [1,3,5,7][1, 3, 5, 7]) and an integer nn, return the count of positive integers that can be formed using only those digits and are at most nn. For digits =[1,3,5,7]= [1, 3, 5, 7] and n=100n = 100, you can form: 1,3,5,71, 3, 5, 7 (one-digit), 11,13,15,...,7711, 13, 15, ..., 77 (two-digit), but nothing three-digit since 111>100111 > 100.

Answer: 2020. This is a clean introduction to digit DP. The only constraint is which digits you can use.