Leetcode Problem 902. Numbers At Most N Given Digit Set

902. Numbers At Most N Given Digit Set

Leetcode Solutions

Dynamic Programming and Counting Approach

  1. Convert the integer n to a string S to easily access its digits.
  2. Initialize a dynamic programming array dp with a length of K+1, where K is the number of digits in n. Set dp[K] to 1, which represents the empty number.
  3. Iterate over the digits of n from left to right, using index i from 0 to K-1.
  4. For each digit S[i] of n, count the number of digits in the given digits array that are less than S[i] and update dp[i] accordingly.
  5. If S[i] is in the digits array, add dp[i+1] to dp[i] to include the count of numbers that start with S[i] and are valid for the remaining digits.
  6. After the loop, dp[0] will contain the total count of valid numbers that are less than or equal to n.
  7. Return dp[0] as the result.
UML Thumbnail

Mathematical Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...