Numbers Of Length N and Values Less Than K

Problem

Given a set of digits (A) in sorted order, find how many numbers of length B are possible whose value is less than number C.

NOTE: All numbers can only have digits from the given set.

Examples

dp

Example 1

Input:
A = [0, 1, 5], B = 1, C = 2
Output: 2
Explanation: Numbers 0 and 1 are possible.

Example 2

Input:
A = [0, 1, 2, 5], B = 2, C = 21
Output: 5
Explanation: Numbers 10, 11, 12, 15, 20 are possible.

Constraints

• 1 ≤ B ≤ 9
• 0 ≤ C ≤ 1e9
• 0 ≤ A[i] ≤ 9

Solution

Method 1 – Combinatorial Counting (Simple Cases)

Intuition

If the number of digits to form is less than the number of digits in C, then any number of length B using the digits in A is valid (with care for leading zeros).

Approach

• If B > number of digits in C or A is empty, return 0.
• If B < number of digits in C, count all valid B-digit numbers:
  • If B == 1, all digits in A are valid (including 0).
  • If A contains 0 and B > 1, first digit cannot be 0.
  • Use combinatorics: (d-1) * d^(B-1) if 0 in A, else d^B.

Complexity

• ⏰ Time complexity: O(1)
• 🧺 Space complexity: O(1)

Method 2 – DP by Digits (When B == len(C))

Intuition

When the number of digits to form is equal to the number of digits in C, we need to count only those numbers less than C. We use digit DP to count valid numbers position by position.

Approach

1. Convert C to its digit array.
2. Precompute for each digit 0-9 how many digits in A are less than or equal to it (prefix sum array).
3. Use DP:
   • dp[i]: number of valid numbers of length i less than the first i digits of C.
   • For each position, consider:
     • Numbers where the prefix is already less than C (can use any digit).
     • Numbers where the prefix matches C so far (can only use digits less than the current digit of C).
   • For the first digit, do not allow 0 if B > 1.
4. The answer is dp[B].

Complexity

• ⏰ Time complexity: O(B)
• 🧺 Space complexity: O(1)

Code

C++

class Solution {
public:
	int solve(vector<int> &A, int B, int C) {
		string S = to_string(C);
		int d = A.size(), n = S.size();
		if (d == 0 || B > n) return 0;
		if (B < n) {
			if (A[0] == 0 && B > 1) return (d-1) * pow(d, B-1);
			return pow(d, B);
		}
		vector<int> digits;
		for (char c : S) digits.push_back(c - '0');
		vector<int> lower(11, 0);
		for (int x : A) lower[x+1] = 1;
		for (int i = 1; i <= 10; i++) lower[i] += lower[i-1];
		int dp = 0, flag = 1;
		for (int i = 0; i < B; i++) {
			int dgt = digits[i];
			int cnt = lower[dgt];
			if (i == 0 && A[0] == 0 && B > 1) cnt--;
			dp = dp * d + flag * cnt;
			flag = flag && (lower[dgt+1] == lower[dgt] + 1);
		}
		return dp;
	}
};

Java

class Solution {
	public int solve(ArrayList<Integer> A, int B, int C) {
		char[] ca = Integer.toString(C).toCharArray();
		if (A.size() == 0 || B > ca.length) return 0;
		if (B < ca.length) {
			if (A.get(0) == 0 && B > 1) return (int)Math.pow(A.size()-1, 1) * (int)Math.pow(A.size(), B-1);
			return (int)Math.pow(A.size(), B);
		}
		int[] lower = new int[11];
		for (int x : A) lower[x+1] = 1;
		for (int i = 1; i <= 10; i++) lower[i] += lower[i-1];
		int dp = 0, flag = 1;
		for (int i = 0; i < B; i++) {
			int dgt = ca[i] - '0';
			int cnt = lower[dgt];
			if (i == 0 && A.get(0) == 0 && B > 1) cnt--;
			dp = dp * A.size() + flag * cnt;
			flag = flag & (lower[dgt+1] == lower[dgt] + 1) ? 1 : 0;
		}
		return dp;
	}
}

Python

class Solution:
	def solve(self, A: list[int], B: int, C: int) -> int:
		S = str(C)
		d, n = len(A), len(S)
		if d == 0 or B > n:
			return 0
		if B < n:
			if A[0] == 0 and B > 1:
				return (d-1) * (d ** (B-1))
			return d ** B
		digits = [int(x) for x in S]
		lower = [0]*11
		for x in A:
			lower[x+1] = 1
		for i in range(1, 11):
			lower[i] += lower[i-1]
		dp, flag = 0, 1
		for i in range(B):
			dgt = digits[i]
			cnt = lower[dgt]
			if i == 0 and A[0] == 0 and B > 1:
				cnt -= 1
			dp = dp * d + flag * cnt
			flag = flag and (lower[dgt+1] == lower[dgt] + 1)
		return dp