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 changesint 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 Codeint 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 approachimport 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 changesdef 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 Codeif __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 approachusing 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> |
Output:Â
6 5
Â
Time Complexity: O(N).
Auxiliary Space: O(N).
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!
… [Trackback]
[…] Read More Information here on that Topic: geeksforgeeks.org/maximize-the-count-of-distinct-elements-in-array-after-at-most-k-changes/ […]
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/maximize-the-count-of-distinct-elements-in-array-after-at-most-k-changes/ […]
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/maximize-the-count-of-distinct-elements-in-array-after-at-most-k-changes/ […]
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/maximize-the-count-of-distinct-elements-in-array-after-at-most-k-changes/ […]