write a program you are given a list of integers and an integers k write an algorithm to find the number of elements in the list that are less than k
Answers
Answer:
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.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
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]].
Finally we return dp[N]. Note: For the first index don’t include 0 if N is not 1 and dp[0]=0.
Below is the implementation of the above approach:
filter_none
edit
play_arrow
brightness_4
// 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;
}
Output:
5
Time complexity: O(N)
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.
Explanation: