1.
Understanding
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
2.4.
Input
2.5.
Output
2.6.
Explanation
3.
Approach 1
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Approach 2
4.1.
Algorithm
4.2.
Program
4.3.
Input
4.4.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Approach 3
5.1.
Algorithm
5.2.
Program
5.3.
Input
5.4.
Output
5.5.
Time Complexity
5.6.
Space Complexity
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Maximize count of distinct elements in a subsequence of size K in given array

## Understanding

This blog discusses a problem based on constructive algorithms. We will take up a coding challenge that requires a better understanding of the problem statement. Such problems are very interesting in nature. You need to have a greater degree of observatory skills to identify the trick to solve the problem. We will discuss various approaches to solve the problem.

## Problem Statement

Ninja has given you an array of ‘N’ integers and an integer ‘K’. Your task is to find the maximum count of distinct integers over all subsequences of length K from the array.

Subsequence of an array

A subsequence of an array is a sequence of numbers formed by deleting some elements from the array without changing the order of the remaining elements. For example,

Given array: {1, 5, 3, 6, 7}

A: {1, 3, 7}

B: {3, 5, 7}

A is a subsequence of the array, whereas B is not. It is because we can create the subsequence A by deleting 5 and 6 from the array. However, we cannot create sequence B without reordering the elements of the array. Hence, B is not a subsequence of the array.

### Input

Enter the values of N and K: 6 5

Enter the elements: 4 6 7 7 3 3

4

### Explanation

We can create the following subsequence: {4, 6, 7, 3} with all distinct elements.

### Input

Enter the values of N and K: 8 5

Enter the elements: 14 16 17 17 13 13 14 16

4

### Explanation

We can create the following subsequence: {14, 16, 17, 13, 13} with four elements. Other subsequences with four distinct elements are: {14, 16, 17, 13, 14}, {17, 13, 13, 14, 16}, etc.

Also see, Euclid GCD Algorithm

## 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

1. Let ‘TOTAL_DISTINCT’ = 0 be the number of distinct elements in the array ‘ARR’.
2. Iterate over the array ‘ARR’ with variable i and do the following:
1. 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.
2. If there is no such j, ‘TOTAL_DISTINCT’ += 1.
3. 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++;

}

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

1. Create a set SET_ARR of integers. Iterate over the given array and insert its elements one by one.
2. 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

1. Create an unordered set SET_ARR of integers. Iterate over the given array and insert its elements one by one.
2. 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:

Live masterclass