Count of integers of length N and value less than K such that they contain digits only from the given set

0 0 11 minutes read

Given a set of digits A[] in sorted order and two integers N and K, the task is to find how many numbers of length N are possible whose value is less than K and the digits are from the given set only. Note that you can use the same digit multiple times.

Examples:

Input: A[] = {0, 1, 5}, N = 1, K = 2
Output: 2
Only valid numbers are 0 and 1.

Input: A[] = {0, 1, 2, 5}, N = 2, K = 21
Output: 5
10, 11, 12, 15 and 20 are the valid numbers.

Approach: Let d be the size of A[]. We can break this problem into three simpler cases.

When N is greater than the length of K, It is obvious that if the length of N is greater than the length of k or if d is equal to 0, no such number is possible.
When N is smaller than the length of K, then all possible combinations of digit of length N are valid. Also, we have to keep in mind that 0 can’t be in the first place. So, if A[] contains 0, the first place can be filled in (d – 1) ways. Since repetition is allowed and 0 can occupy the other places, rest N – 1 places can be filled in d * d * … * d(N – 1) times i.e. in d^{N – 1} ways. Therefore the answer is (d – 1) * (d^{N – 1}) if A[] contains 0 else d^N.
When N is equal to the length of K, this is the trickiest part. We need to use Dynamic Programming for this part. Construct a digit array of K. Let’s call it digit[]. Let First(i) be the number formed by taking the first i digits of it. Let lower[i] denote the number of elements in A[] which are smaller than i.
For example, First(2) of 423 is 42. If A[] = {0, 2} then lower[0] = 0, lower[1] = 1, lower[2] = 1, lower[3] = 2.
Generate N digit numbers by dynamic programming. Let dp[i] denote total numbers of length i which are less than first i digits of K.
Elements in dp[i] can be generated by two cases:
- For all the numbers whose First(i – 1) is less than First(i – 1) of K, we can put any digit at i^th index. Hence, dp[i] = dp[i] + (dp[i – 1] * d)
- For all the numbers whose First(i – 1) is the same as First(i – 1) of K, we can only put those digits which are smaller than digit[i]. Hence, dp[i] = dp[i] + lower[digit[i]].

Below is the implementation of the above approach:

C++14

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 10
 
// Function to convert a number into vector
vector<int> numToVec(int N)
{
    vector<int> digit;
 
    // Push all the digits of N from the end
    // one by one to the vector
    while (N != 0) {
        digit.push_back(N % 10);
        N = N / 10;
    }
 
    // If the original number was 0
    if (digit.size() == 0)
        digit.push_back(0);
 
    // Reverse the vector elements
    reverse(digit.begin(), digit.end());
 
    // Return the required vector
    return digit;
}
 
// Function to return the count of B length integers
// which are less than C and they
// contain digits from set A[] only
int solve(vector<int>& A, int B, int C)
{
    vector<int> digit;
    int d, d2;
 
    // Convert number to digit array
    digit = numToVec(C);
    d = A.size();
 
    // Case 1: No such number possible as the
    // generated numbers will always
    // be greater than C
    if (B > digit.size() || d == 0)
        return 0;
 
    // Case 2: All integers of length B are valid
    // as they all are less than C
    else if (B < digit.size()) {
        // contain 0
        if (A[0] == 0 && B != 1)
            return (d - 1) * pow(d, B - 1);
        else
            return pow(d, B);
    }
 
    // Case 3
    else {
        int dp[B + 1] = { 0 };
        int lower[MAX + 1] = { 0 };
 
        // Update the lower[] array such that
        // lower[i] stores the count of elements
        // in A[] which are less than i
        for (int i = 0; i < d; i++)
            lower[A[i] + 1] = 1;
        for (int i = 1; i <= MAX; i++)
            lower[i] = lower[i - 1] + lower[i];
 
        bool flag = true;
        dp[0] = 0;
        for (int i = 1; i <= B; i++) {
            d2 = lower[digit[i - 1]];
            dp[i] = dp[i - 1] * d;
 
            // For first index we can't use 0
            if (i == 1 && A[0] == 0 && B != 1)
                d2 = d2 - 1;
 
            // Whether (i-1) digit of generated number
            // can be equal to (i - 1) digit of C
            if (flag)
                dp[i] += d2;
 
            // Is digit[i - 1] present in A ?
            flag = (flag & (lower[digit[i - 1] + 1]
                            == lower[digit[i - 1]] + 1));
        }
        return dp[B];
    }
}
 
// Driver code
int main()
{
 
    // Digits array
    vector<int> A = { 0, 1, 2, 5 };
    int N = 2;
    int k = 21;
 
    cout << solve(A, N, k);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
static int MAX = 10;
 
// Function to convert a number into vector
static Vector<Integer> numToVec(int N)
{
    Vector<Integer> digit = new Vector<Integer>();
 
    // Push all the digits of N from the end
    // one by one to the vector
    while (N != 0)
    {
        digit.add(N % 10);
        N = N / 10;
    }
 
    // If the original number was 0
    if (digit.size() == 0)
        digit.add(0);
 
    // Reverse the vector elements
    Collections.reverse(digit);
 
    // Return the required vector
    return digit;
}
 
// Function to return the count 
// of B length integers which are 
// less than C and they contain 
// digits from set A[] only
static int solve(Vector<Integer> A, int B, int C)
{
    Vector<Integer> digit = new Vector<Integer>();
    int d, d2;
 
    // Convert number to digit array
    digit = numToVec(C);
    d = A.size();
 
    // Case 1: No such number possible as the
    // generated numbers will always
    // be greater than C
    if (B > digit.size() || d == 0)
        return 0;
 
    // Case 2: All integers of length B are valid
    // as they all are less than C
    else if (B < digit.size()) 
    {
        // contain 0
        if (A.get(0) == 0 && B != 1)
            return (int) ((d - 1) * Math.pow(d, B - 1));
        else
            return (int) Math.pow(d, B);
    }
 
    // Case 3
    else
    {
        int []dp = new int[B + 1];
        int []lower = new int[MAX + 1];
 
        // Update the lower[] array such that
        // lower[i] stores the count of elements
        // in A[] which are less than i
        for (int i = 0; i < d; i++)
            lower[A.get(i) + 1] = 1;
        for (int i = 1; i <= MAX; i++)
            lower[i] = lower[i - 1] + lower[i];
 
        boolean flag = true;
        dp[0] = 0;
        for (int i = 1; i <= B; i++) 
        {
            d2 = lower[digit.get(i - 1)];
            dp[i] = dp[i - 1] * d;
 
            // For first index we can't use 0
            if (i == 1 && A.get(0) == 0 && B != 1)
                d2 = d2 - 1;
 
            // Whether (i-1) digit of generated number
            // can be equal to (i - 1) digit of C
            if (flag)
                dp[i] += d2;
 
            // Is digit[i - 1] present in A ?
            flag = (flag & (lower[digit.get(i - 1) + 1] == 
                            lower[digit.get(i - 1)] + 1));
        }
        return dp[B];
    }
}
 
// Driver code
public static void main(String[] args) 
{
    Integer arr[] = { 0, 1, 2, 5 };
    // Digits array
    Vector<Integer> A = new Vector<>(Arrays.asList(arr));
    int N = 2;
    int k = 21;
 
    System.out.println(solve(A, N, k));
}
}
 
// This code is contributed
// by PrinciRaj1992 

Python3

# Python3 implementation of the approach
MAX=10
 
# Function to convert a number into vector
def numToVec(N):
     
    digit = []
 
    # Push all the digits of N from the end
    # one by one to the vector
    while (N != 0):
        digit.append(N % 10)
        N = N // 10
 
    # If the original number was 0
    if (len(digit) == 0):
        digit.append(0)
 
    # Reverse the vector elements
    digit = digit[::-1]
 
    # Return the required vector
    return digit
 
 
# Function to return the count of B length integers
# which are less than C and they
# contain digits from set A[] only
def solve(A, B, C):
    d, d2 = 0,0
 
    # Convert number to digit array
    digit = numToVec(C)
    d = len(A)
 
    # Case 1: No such number possible as the
    # generated numbers will always
    # be greater than C
    if (B > len(digit) or d == 0):
        return 0
 
    # Case 2: All integers of length B are valid
    # as they all are less than C
    elif (B < len(digit)):
        # contain 0
        if (A[0] == 0 and B != 1):
            return (d - 1) * pow(d, B - 1)
        else:
            return pow(d, B)
 
    # Case 3
    else :
        dp=[0 for i in range(B + 1)]
        lower=[0 for i in range(MAX + 1)]
 
        # Update the lower[] array such that
        # lower[i] stores the count of elements
        # in A[] which are less than i
        for i in range(d):
            lower[A[i] + 1] = 1
        for i in range(1, MAX+1):
            lower[i] = lower[i - 1] + lower[i]
 
        flag = True
        dp[0] = 0
        for i in range(1, B+1):
            d2 = lower[digit[i - 1]]
            dp[i] = dp[i - 1] * d
 
            # For first index we can't use 0
            if (i == 1 and A[0] == 0 and B != 1):
                d2 = d2 - 1
 
            # Whether (i-1) digit of generated number
            # can be equal to (i - 1) digit of C
            if (flag):
                dp[i] += d2
 
            # Is digit[i - 1] present in A ?
            flag = (flag & (lower[digit[i - 1] + 1] == lower[digit[i - 1]] + 1))
         
        return dp[B]
 
# Driver code
 
# Digits array
A =[0, 1, 2, 5]
N = 2
k = 21
 
print(solve(A, N, k))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG 
{
static int MAX = 10;
 
// Function to convert a number into vector
static List<int> numToVec(int N)
{
    List<int> digit = new List<int>();
 
    // Push all the digits of N from the end
    // one by one to the vector
    while (N != 0)
    {
        digit.Add(N % 10);
        N = N / 10;
    }
 
    // If the original number was 0
    if (digit.Count == 0)
        digit.Add(0);
 
    // Reverse the vector elements
    digit.Reverse();
 
    // Return the required vector
    return digit;
}
 
// Function to return the count 
// of B length integers which are 
// less than C and they contain 
// digits from set A[] only
static int solve(List<int> A, int B, int C)
{
    List<int> digit = new List<int>();
    int d, d2;
 
    // Convert number to digit array
    digit = numToVec(C);
    d = A.Count;
 
    // Case 1: No such number possible as the
    // generated numbers will always
    // be greater than C
    if (B > digit.Count || d == 0)
        return 0;
 
    // Case 2: All integers of length B are valid
    // as they all are less than C
    else if (B < digit.Count) 
    {
        // contain 0
        if (A[0] == 0 && B != 1)
            return (int) ((d - 1) * Math.Pow(d, B - 1));
        else
            return (int) Math.Pow(d, B);
    }
 
    // Case 3
    else
    {
        int []dp = new int[B + 1];
        int []lower = new int[MAX + 1];
 
        // Update the lower[] array such that
        // lower[i] stores the count of elements
        // in A[] which are less than i
        for (int i = 0; i < d; i++)
            lower[A[i] + 1] = 1;
        for (int i = 1; i <= MAX; i++)
            lower[i] = lower[i - 1] + lower[i];
 
        Boolean flag = true;
        dp[0] = 0;
        for (int i = 1; i <= B; i++) 
        {
            d2 = lower[digit[i-1]];
            dp[i] = dp[i - 1] * d;
 
            // For first index we can't use 0
            if (i == 1 && A[0] == 0 && B != 1)
                d2 = d2 - 1;
 
            // Whether (i-1) digit of generated number
            // can be equal to (i - 1) digit of C
            if (flag)
                dp[i] += d2;
 
            // Is digit[i - 1] present in A ?
            flag = (flag & (lower[digit[i-1] + 1] == 
                            lower[digit[i-1]] + 1));
        }
        return dp[B];
    }
}
 
// Driver code
public static void Main(String[] args) 
{
    int []arr = { 0, 1, 2, 5 };
     
    // Digits array
    List<int> A = new List<int>(arr);
    int N = 2;
    int k = 21;
 
    Console.WriteLine(solve(A, N, k));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
let MAX = 10;
 
// Function to convert a number into vector
function numToVec(N)
{
    let digit = [];
         
    // Push all the digits of N from the end
    // one by one to the vector
    while (N != 0)
    {
        digit.push(N % 10);
        N = Math.floor(N / 10);
    }
   
    // If the original number was 0
    if (digit.length == 0)
        digit.push(0);
   
    // Reverse the vector elements
    digit.reverse();
   
    // Return the required vector
    return digit;
}
 
// Function to return the count 
// of B length integers which are 
// less than C and they contain 
// digits from set A[] only
function solve(A, B, C)
{
    let digit = [];
    let d, d2;
   
    // Convert number to digit array
    digit = numToVec(C);
    d = A.length;
   
    // Case 1: No such number possible as the
    // generated numbers will always
    // be greater than C
    if (B > digit.length || d == 0)
        return 0;
   
    // Case 2: All integers of length B are valid
    // as they all are less than C
    else if (B < digit.length) 
    {
         
        // contain 0
        if (A[0] == 0 && B != 1)
            return  Math.floor((d - 1) * 
                    Math.pow(d, B - 1));
        else
            return Math.floor(Math.pow(d, B));
    }
   
    // Case 3
    else
    {
        let dp = new Array(B + 1);
        let lower = new Array(MAX + 1);
         
          for(let i = 0; i < dp.length; i++)
        {
            dp[i] = 0;
        }
        for(let i = 0; i < lower.length; i++)
        {
            lower[i] = 0;
        }
         
        // Update the lower[] array such that
        // lower[i] stores the count of elements
        // in A[] which are less than i
        for(let i = 0; i < d; i++)
            lower[A[i] + 1] = 1;
        for(let i = 1; i <= MAX; i++)
            lower[i] = lower[i - 1] + lower[i];
   
        let flag = true;
        dp[0] = 0;
        for(let i = 1; i <= B; i++) 
        {
            d2 = lower[digit[i - 1]];
            dp[i] = dp[i - 1] * d;
   
            // For first index we can't use 0
            if (i == 1 && A[0] == 0 && B != 1)
                d2 = d2 - 1;
   
            // Whether (i-1) digit of generated number
            // can be equal to (i - 1) digit of C
            if (flag)
                dp[i] += d2;
   
            // Is digit[i - 1] present in A ?
            flag = (flag & (lower[digit[i - 1] + 1] == 
                            lower[digit[i - 1]] + 1));
        }
        return dp[B];
    }
}
 
// Driver code
let arr = [ 0, 1, 2, 5 ];
let N = 2;
let k = 21;
 
document.write(solve(arr, N, k));
     
// This code is contributed by patel2127
 
</script>

Output:

Time complexity: O(N)
Auxiliary Space: O(N), since N extra space has been taken.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!