Operaciones mínimas requeridas para hacer que todos los elementos sean distintos en una array

Dada una array de N enteros. Si un número aparece más de una vez, elija cualquier número y de la array y reemplace la x en la array por x+y de modo que x+y no esté en la array. La tarea es encontrar el número mínimo de operaciones para hacer que la array sea distinta. 
Ejemplos: 
 

Entrada: a[] = {2, 1, 2} 
Salida: 1 
Sea x = 2, y = 1 y luego reemplace 2 por 3. 
Al realizar el paso anterior, todos los elementos de la array son distintos. 
Entrada: a[] = {1, 2, 3} 
Salida: 0

Enfoque: si un número aparece más de una vez, entonces la suma de (ocurrencias-1) para todos los elementos duplicados será la respuesta. La lógica principal detrás de esto es que si x se reemplaza por x+y, donde y es el elemento más grande de la array, entonces x se reemplaza por x+y, que es el elemento más grande de la array. Use un mapa para almacenar la frecuencia de los números de la array. Recorra el mapa, y si la frecuencia de un elemento es mayor que 1, agréguelo a la cuenta restando uno. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find Minimum number
// of  changes to make array distinct
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns minimum number of changes
int minimumOperations(int a[], int n)
{
 
    // Hash-table to store frequency
    unordered_map<int, int> mp;
 
    // Increase the frequency of elements
    for (int i = 0; i < n; i++)
        mp[a[i]] += 1;
 
    int count = 0;
 
    // Traverse in the map to sum up the (occurrences-1)
    // of duplicate elements
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if ((*it).second > 1)
            count += (*it).second-1;
    }
    return count;
}
 
// Driver Code
int main()
{
    int a[] = { 2, 1, 2, 3, 3, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << minimumOperations(a, n);
    return 0;
}

// Java program to find Minimum number
// of changes to make array distinct
import java.util.*;
 
class geeks
{
 
    // Function that returns minimum number of changes
    public static int minimumOperations(int[] a, int n)
    {
 
        // Hash-table to store frequency
        HashMap<Integer, Integer> mp = new HashMap<>();
 
        // Increase the frequency of elements
        for (int i = 0; i < n; i++)
        {
            if (mp.get(a[i]) != null)
            {
                int x = mp.get(a[i]);
                mp.put(a[i], ++x);
            }
            else
                mp.put(a[i], 1);
        }
 
        int count = 0;
 
        // Traverse in the map to sum up the (occurrences-1)
        // of duplicate elements
        for (HashMap.Entry<Integer, Integer> entry : mp.entrySet())
        {
            if (entry.getValue() > 1)
            {
                count += (entry.getValue() - 1);
            }
        }
 
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] a = { 2, 1, 2, 3, 3, 4, 3 };
        int n = a.length;
 
        System.out.println(minimumOperations(a, n));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to find Minimum number
# of changes to make array distinct
 
# Function that returns minimum
# number of changes
def minimumOperations(a, n):
 
    # Hash-table to store frequency
    mp = dict()
 
    # Increase the frequency of elements
    for i in range(n):
        if a[i] in mp.keys():
            mp[a[i]] += 1
        else:
            mp[a[i]] = 1
 
    count = 0
 
    # Traverse in the map to sum up the
    # (occurrences-1)of duplicate elements
    for it in mp:
        if (mp[it] > 1):
            count += mp[it] - 1
     
    return count
 
# Driver Code
a = [2, 1, 2, 3, 3, 4, 3 ]
n = len(a)
 
print(minimumOperations(a, n))
     
# This code is contributed
# by Mohit Kumar

// C# program to find Minimum number
// of changes to make array distinct
using System;
using System.Collections.Generic;
 
class geeks
{
 
    // Function that returns minimum number of changes
    public static int minimumOperations(int[] a, int n)
    {
 
        // Hash-table to store frequency
        Dictionary<int,int> mp = new Dictionary<int,int>();
        // Increase the frequency of elements
        for (int i = 0 ; i < n; i++)
        {
            if(mp.ContainsKey(a[i]))
            {
                var val = mp[a[i]];
                mp.Remove(a[i]);
                mp.Add(a[i], val + 1);
            }
            else
            {
                mp.Add(a[i], 1);
            }
        }
 
        int count = 0;
 
        // Traverse in the map to sum up the (occurrences-1)
        // of duplicate elements
        foreach(KeyValuePair<int, int> entry in mp)
        {
            if (entry.Value > 1)
            {
                count += (entry.Value - 1);
            }
        }
 
        return count;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = { 2, 1, 2, 3, 3, 4, 3 };
        int n = a.Length;
 
        Console.WriteLine(minimumOperations(a, n));
    }
}
 
/* This code is contributed by PrinciRaj1992 */

<script>
 
// JavaScript program to find Minimum number
// of changes to make array distinct
     
    // Function that returns minimum
    // number of changes
    function minimumOperations(a,n)
    {
        // Hash-table to store frequency
        let mp = new Map();
   
        // Increase the frequency of elements
        for (let i = 0; i < n; i++)
        {
            if (mp.get(a[i]) != null)
            {
                let x = mp.get(a[i]);
                mp.set(a[i], ++x);
            }
            else
                mp.set(a[i], 1);
        }
   
        let count = 0;
   
        // Traverse in the map to
        // sum up the (occurrences-1)
        // of duplicate elements
        for (let [key, value] of mp.entries())
        {
            if (value > 1)
            {
                count += (value - 1);
            }
        }
   
        return count;
    }
     
    // Driver Code
    let a=[2, 1, 2, 3, 3, 4, 3];
    let n = a.length;
     
    document.write(minimumOperations(a, n));
     
// This code is contributed by patel2127
 
</script>

3

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.

Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.