Approach 1
Can you guess the relation between the desired answer and the number of distinct elements in the given array? Yeah, you got it right. The answer to this problem is min(Number of distinct elements in the array, ‘K’). There are two cases:
Case 1: Number of distinct elements in the array >= K.
Solution: Create a subsequence of ‘K’ elements with ‘K’ distinct elements from the array in the same order they appear in the array. Hence the answer is ‘K’, which is the maximum over all subsequences.
Case 2: Number of distinct elements in the array < K.
Solution: Let the number of distinct elements in the array be D(<K). Create a subsequence of K elements with all these D elements and include K - D elements from the array in the same order as they appear. Hence, the answer is D = min(K, D). It is also the maximum over all subsequences as in any subsequence; we cannot have more than D distinct elements.
Now, the task is to find the number of distinct elements in the array. This can be done in many ways.
Iterate over the array, and for each element, check if it has occurred before. Suppose this is not the case; increment the count of distinct numbers by one.
Algorithm
- Let ‘TOTAL_DISTINCT’ = 0 be the number of distinct elements in the array ‘ARR’.
-
Iterate over the array ‘ARR’ with variable i and do the following:
- Iterate from 0 to i - 1 with variable j and check if ‘ARR[j]’ is equal to ‘ARR[i]’ for any j from 0 to i - 1.
- If there is no such j, ‘TOTAL_DISTINCT’ += 1.
- Output min(‘TOTAL_DISTINCT’, ‘K’).
Program
#include<iostream>
using namespace std;
int countDistinctElem(int n, int K, int arr[]){
// Count of distinct elements.
int totalDistinct = 0;
for(int i = 0; i < n; i++)
{
// Copy of current element exists or not.
bool copy = false;
for(int j = 0; j < i; j++)
{
// If the current element is already present before.
if(arr[j] == arr[i]){
copy = true;
}
}
// If there is no copy of the current element.
if(copy == false) totalDistinct++;
}
// Print the answer.
return min(K, totalDistinct);
}
int main()
{
// Input N and K.
int N, K;
cout<<"Enter the values of N and K: ";
cin>>N>>K;
// Input array.
int arr[N];
cout<<"Enter the elements: ";
for(int i = 0; i < N; i++)
{
cin>>arr[i];
}
int totalDistinct = countDistinctElem(N, K, arr);
cout<<totalDistinct<<endl;
}
Input
Enter the values of N and K: 8 5
Enter the elements: 14 16 17 17 13 13 14 16
Output
4
Time Complexity
The time complexity of the above approach is O(N^2), where N is the number of elements in the array.
It is because we are using two nested loops to check for uniqueness.
Space Complexity
The space complexity of the above approach is O(1), as we are using constant memory in the implementation.
Approach 2
Create a set container and insert the elements of the array into it one by one. The number of distinct elements in the array will be the size of the set at the end.
Algorithm
- Create a set SET_ARR of integers. Iterate over the given array and insert its elements one by one.
- Output min(size(SET_ARR), K).
Program
#include<iostream>
#include<set>
using namespace std;
int countDistinctElem(int n, int K, int arr[]){
// Create an empty set container.
set<int> setArr;
for(int i = 0; i < n; i++)
{
// Insert the current element.
setArr.insert(arr[i]);
}
// Print the answer as described in the approach.
return min((int)setArr.size(), K);
}
int main()
{
// Input N and K.
int N, K;
cout<<"Enter the values of N and K: ";
cin>>N>>K;
// Input array.
int arr[N];
cout<<"Enter the elements: ";
for(int i = 0; i < N; i++)
{
cin>>arr[i];
}
int totalDistinct = countDistinctElem(N, K, arr);
cout<<totalDistinct<<endl;
}
Input
Enter the values of N and K: 8 5
Enter the elements: 14 16 17 17 13 13 14 16
Output
4
Time Complexity
The time complexity of the above approach is O(N*log(N)), where ‘N’ is the number of elements in the array.
It is because the time complexity of insert operation in a set container is log(N), where ‘N’ is the number of elements in the set, and we are calling insert function ‘N’ times.
Space Complexity
The space complexity of the above approach is O(N), as the set size can grow as large as the size of the array if all the array elements are unique.
Approach 3
Create an unordered set (or HashMap in Java) container and insert the elements of the array into it one by one. The number of distinct elements in the array will be the size of the unordered set at the end.
Algorithm
- Create an unordered set SET_ARR of integers. Iterate over the given array and insert its elements one by one.
- Output min(size(SET_ARR), K).
Program
#include<iostream>
#include<unordered_set>
using namespace std;
int countDistinctElem(int n, int K, int arr[]){
// Create an empty set container.
unordered_set<int> setArr;
for(int i = 0; i < n; i++)
{
// Insert the current element.
setArr.insert(arr[i]);
}
// Print the answer as described in the approach.
return min((int)setArr.size(), K);
}
int main()
{
// Input N and K.
int N, K;
cout<<"Enter the values of N and K: ";
cin>>N>>K;
// Input array.
int arr[N];
cout<<"Enter the elements: ";
for(int i = 0; i < N; i++)
{
cin>>arr[i];
}
int totalDistinct = countDistinctElem(N, K, arr);
cout<<totalDistinct<<endl;
}
Input
Enter the values of N and K: 8 5
Enter the elements: 14 16 17 17 13 13 14 16
Output
4
Time Complexity
The time complexity of the above approach is O(N), where ‘N’ is the number of elements in the array.
It is because the time complexity of insert operation in an unordered set container is O(1), and we are calling insert function N times.
Space Complexity
The space complexity of the above approach is O(N), as the set size can grow as large as the size of the array if all the array elements are unique.
Key Takeaways
This blog discussed an exciting problem involving a greater degree of consciousness. We discussed various approaches to solve the problem with time complexities varying from O(N^2) to O(N). There are several such types of constructive problems involving tricky observations.
Hence, learning never stops. So head over to our platform Coding Ninjas Studio to practice problems based on such observations and ace your coding tests and interviews.
Recommended Problems:
38+ registered 