Maximize the count of distinct elements in Array after at most K changes
Given an array arr[], the task is to find the maximum number of distinct numbers in arr after at most K changes. In each change pick any element X from arr and change it to Y such that L <= Y <= R.
Examples:
Input: arr[] = {1, 2, 1, 4, 6, 4, 4}, L = 1, R = 5 and K = 2
Output: 6
Explanation:Following are the operations performed on the given array elements:
1. Changing arr[2] to 3 modifies array to {1, 2, 3, 4, 6, 4, 4}
2. Changing arr[3] to 5 modifies array to {1, 2, 3, 5, 6, 4, 4}As K = 2, no more changes can be done
Therefore, Distinct elements are {1, 2, 3, 5, 6, 4} and the number of maximum distinct elements is 6.Input: arr[] = {1, 2, 1, 4, 6, 4, 4}, L = 1, R = 5 and K = 1
Output: 5
Explanation:Following are the operations performed on the given array elements:
1. Changing arr[2] to 3 modifies array to {1, 2, 3, 4, 6, 4, 4}
As K = 1, no more changes can be done
Therefore, Distinct elements are {1, 2, 3, 6, 4} and the number of maximum distinct elements is 5.
Approach: This problem can be solved by using an unordered map. Store frequency of all the elements in the map and then traverse from L to R, see which number is not already present in the map we can use that number to replace any duplicate element in arr.
- At first, store the frequency of all the elements in the map.
- Total distinct elements will be equal to the size of the map.
- The number of extra elements will be equal to the (size of array – size of map).
- Then iterate from L to R and check how many elements inside this range can be used to replace the extra elements present in the array.
- Update the map for each change in any extra element to any other value.
- At last, the size of the map will be containing all the distinct elements.
- Return the size of the map as the answer.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate // maximum distinct elements possible // after at most K changes int maxDistinctElements( int * arr, int K, int L, int R, int n) { // Map to store frequency of all the elements unordered_map< int , int > frequency; // Count frequency of each element for ( int x = 0; x < n; x++) { frequency[arr[x]] += 1; } // To store number of extra elements // that needs to be changed int extra = (n - frequency.size()); // Traverse from L to R // and see which number is not // present in map, use that number // to change extra duplicate element for ( int i = L; i <= R and K != 0 and extra != 0; i++) { if (!frequency[i]) { frequency[i] = 1; K--; extra--; } } // Total distinct element will be equal // to the size of updated frequency map. int ans = frequency.size(); // Return answer return ans; } // Driver Code int main() { // Test case 1 int N = 7, L = 1, R = 5, K = 2; int arr[7] = { 1, 2, 1, 4, 6, 4, 4 }; cout << maxDistinctElements(arr, K, L, R, N) << endl; // Test case 2 K = 1; cout << maxDistinctElements(arr, K, L, R, N) << endl; } |
Java
// Java program for above approach import java.util.*; class GFG { // Function to calculate // maximum distinct elements possible // after at most K changes static int maxDistinctElements( int [] arr, int K, int L, int R, int n) { // Map to store frequency of all the elements HashMap<Integer, Integer> frequency = new HashMap<Integer, Integer>(); // Count frequency of each element for ( int x = 0 ; x < n; x++) { if (frequency.containsKey(arr[x])) { frequency.put(arr[x], frequency.get(arr[x]) + 1 ); } else { frequency.put(arr[x], 1 ); } } // To store number of extra elements // that needs to be changed int extra = (n - frequency.size()); // Traverse from L to R // and see which number is not // present in map, use that number // to change extra duplicate element for ( int i = L; i <= R && K != 0 && extra != 0 ; i++) { if (!frequency.containsKey(i)) { frequency.put(i, 1 ); K--; extra--; } } // Total distinct element will be equal // to the size of updated frequency map. int ans = frequency.size(); // Return answer return ans; } // Driver Code public static void main(String[] args) { // Test case 1 int N = 7 , L = 1 , R = 5 , K = 2 ; int arr[] = { 1 , 2 , 1 , 4 , 6 , 4 , 4 }; System.out.print(maxDistinctElements(arr, K, L, R, N) + "\n" ); // Test case 2 K = 1 ; System.out.print(maxDistinctElements(arr, K, L, R, N) + "\n" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program for above approach # Function to calculate # maximum distinct elements possible # after at most K changes def maxDistinctElements(arr, K, L, R, n): # Map to store frequency of all the elements frequency = {} # Count frequency of each element for x in range (n): if arr[x] in frequency: frequency[arr[x]] + = 1 else : frequency[arr[x]] = 1 # To store number of extra elements # that needs to be changed extra = (n - len (frequency)) # Traverse from L to R # and see which number is not # present in map, use that number # to change extra duplicate element i = L while (i < = R and K ! = 0 and extra ! = 0 ): if (i not in frequency): frequency[i] = 1 K - = 1 extra - = 1 else : frequency[i] = 1 i + = 1 # Total distinct element will be equal # to the size of updated frequency map. ans = len (frequency) # Return answer return ans # Driver Code if __name__ = = '__main__' : # Test case 1 N = 7 L = 1 R = 5 K = 2 arr = [ 1 , 2 , 1 , 4 , 6 , 4 , 4 ] print (maxDistinctElements(arr, K, L, R, N)) # Test case 2 K = 1 print (maxDistinctElements(arr, K, L, R, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG { // Function to calculate // maximum distinct elements possible // after at most K changes static int maxDistinctElements( int [] arr, int K, int L, int R, int n) { // Map to store frequency of all the elements Dictionary< int , int > frequency = new Dictionary< int , int >(); // Count frequency of each element for ( int x = 0; x < n; x++) { if (frequency.ContainsKey(arr[x])) frequency[arr[x]] += 1; else frequency[arr[x]] = 1; } // To store number of extra elements // that needs to be changed int extra = (n - frequency.Count); // Traverse from L to R // and see which number is not // present in map, use that number // to change extra duplicate element for ( int i = L; i <= R && K != 0 && extra != 0; i++) { if (!frequency.ContainsKey(i)) { frequency[i] = 1; K--; extra--; } } // Total distinct element will be equal // to the size of updated frequency map. int ans = frequency.Count; // Return answer return ans; } // Driver Code public static void Main() { // Test case 1 int N = 7, L = 1, R = 5, K = 2; int [] arr = { 1, 2, 1, 4, 6, 4, 4 }; Console.WriteLine( maxDistinctElements(arr, K, L, R, N)); // Test case 2 K = 1; Console.WriteLine( maxDistinctElements(arr, K, L, R, N)); } } // This code is contributed by decode2207. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate // maximum distinct elements possible // after at most K changes function maxDistinctElements(arr, K, L, R, n) { // Map to store frequency of all the elements let frequency = new Map(); // Count frequency of each element for (let x = 0; x < n; x++) { if (frequency.has(arr[x])) { frequency.set(frequency.get(arr[x]), frequency.get(arr[x]) + 1); } else { frequency.set(arr[x], 1) } } // To store number of extra elements // that needs to be changed let extra = (n - frequency.size); // Traverse from L to R // and see which number is not // present in map, use that number // to change extra duplicate element for (let i = L; i <= R && K != 0 && extra != 0; i++) { if (!frequency.has(i)) { frequency.set(i, 1); K--; extra--; } } // Total distinct element will be equal // to the size of updated frequency map. let ans = frequency.size; // Return answer return ans; } // Driver Code // Test case 1 let N = 7, L = 1, R = 5, K = 2; let arr = [1, 2, 1, 4, 6, 4, 4]; document.write(maxDistinctElements(arr, K, L, R, N) + "<br>" ); // Test case 2 K = 1; document.write(maxDistinctElements(arr, K, L, R, N) + "<br>" ); // This code is contributed by Potta Lokesh </script> |
6 5
Time Complexity: O(N).
Auxiliary Space: O(N).