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 dN – 1 ways. Therefore the answer is (d – 1) * (dN – 1) if A[] contains 0 else dN.
- 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 ith 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 vectorvector<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[] onlyint 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 codeint 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 approachimport java.util.*;class GFG {static int MAX = 10;// Function to convert a number into vectorstatic 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[] onlystatic 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 codepublic 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 approachMAX=10# Function to convert a number into vectordef 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[] onlydef 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 arrayA =[0, 1, 2, 5]N = 2k = 21print(solve(A, N, k))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG {static int MAX = 10;// Function to convert a number into vectorstatic 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[] onlystatic 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 codepublic 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 approachlet MAX = 10;// Function to convert a number into vectorfunction 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[] onlyfunction 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 codelet 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:
5
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
