Numbers At Most N Given Digit Set

Problem Statement

In this problem, we are provided with a list of digits, each represented as a string and sorted in a non-decreasing order. The goal is to determine how many distinct positive integers can be created using any combination of these digits, such that each digit can be used repeatedly, and the resulting number is less than or equal to a specified integer n. The challenge is to consider each possible combination of digits that forms numbers within the permitted range.

Examples

Example 1

Input:

digits = ["1","3","5","7"], n = 100

Output:

20

Explanation:

The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2

Input:

digits = ["1","4","9"], n = 1000000000

Output:

29523

Explanation:

We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.

Example 3

Input:

digits = ["7"], n = 8

Output:

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 <= 109

Approach and Intuition

The task involves generating numbers using the given digits such that these numbers are within a specified limit n. Here's how we can intuitively approach this problem:

1. Identify Lengths to Consider: Determine the number of digits (or length) of the maximum allowable number (which is n). This gives us an upper boundary on the lengths of numbers we need to consider.

2. Count Valid Combinations for Each Length:

   • For each possible length from 1 up to the number of digits in n, we calculate how many numbers can be formed using the given digits.
   • For instance, if digits = ['1', '3', '5'] and n = 100, we would consider numbers of length 1 and 2.

3. Address Edge Cases with Upper Limit:

   • When the length of the number matches that of n, special care is needed to ensure none of the generated numbers exceed n.
   • This typically requires comparing these numbers digit-by-digit from the most significant digit against n.

4. Sum Up Combinations: Sum the valid combinations for each length to get the total count of numbers that can be generated within the bounds set by n.

For example, in Example 1:

• For 1-digit numbers, all digits ["1", "3", "5", "7"] are valid since 7 (the highest in the set) is less than 100.
• For 2-digit numbers, combinations like "11", "13", etc., can be made easily as they do not exceed 100. When we reach combinations that might breach 100 (like starting with '9' or '8' which are not in our list), those are excluded.

This approach ensures we count all valid numbers that can be crafted using the given digits without exceeding the number n. The computational challenge lies in efficiently handling the combinations and ensuring the counts are correct especially for numbers close to the limit n.

Solutions

class Solution {
    public int maxDigitsWithinLimit(String[] digits, int limit) {
        int base = digits.length; // representing the base calculation
        char[] charsOfN = String.valueOf(limit).toCharArray();
        int len = charsOfN.length;
        int[] digitPositions = new int[len];
        int idx = 0;
    
        for (char digit : charsOfN) {
            int pos = 0;
            boolean isPresent = false;
            for (int j = 0; j < base; ++j) {
                if (digit >= digits[j].charAt(0))
                    pos = j + 1;
                if (digit == digits[j].charAt(0))
                    isPresent = true;
            }
    
            digitPositions[idx++] = pos;
            if (isPresent) continue;
    
            if (pos == 0) {
                for (int k = idx - 1; k > 0; --k) {
                    if (digitPositions[k] > 0) break;
                    digitPositions[k] += base;
                    digitPositions[k - 1]--;
                }
            }
    
            while (idx < len)
                digitPositions[idx++] = base;
            break;
        }
    
        int result = 0;
        for (int num : digitPositions)
            result = result * base + num;
        return result;
    }
}