Reemplazar duplicados con un valor duplicado mayor que el anterior

Dada una array de elementos y cambie la array de tal manera que todos los elementos de la array sean distintos. Si está reemplazando un valor, entonces el valor de reemplazo debe ser mayor que el valor anterior y, después de la modificación, la suma de los elementos debe ser lo más pequeña posible.

Ejemplos: 

Entrada: arr = {1, 2, 2, 5, 8, 8, 8} 
Salida: 1 2 3 5 8 9 10 
8 se reemplaza con 9 (Un elemento inexistente mayor que 8). A continuación, la ocurrencia duplicada de 8 se reemplaza con 10.

Entrada: arr = {1, 2, 5, 7, 8, 8, 7} 
Salida: 1 2 5 7 8 9 10

Entrada: arr = {9, 9, 9, 9, 9} 
Salida: 9 10 11 12 13 

Fuente : experiencia de entrevista de Paytm 30 .

Este problema es una variación de este artículo. En el artículo anterior, tuvimos que reemplazar los duplicados con el mayor valor hasta el momento. Pero en este problema, tenemos que reemplazar elementos con duplicados mayores que el valor duplicado anterior. 
La idea es encontrar el siguiente elemento mayor a reemplazar para minimizar la suma total. Para encontrar el siguiente elemento mayor, tenemos que iterar desde el elemento repetido hasta INT_MAX hasta encontrar el siguiente elemento mayor.

A continuación se muestra la implementación del enfoque anterior.  

// CPP program to replace every repeating
// element with next greater element.
#include <bits/stdc++.h>
using namespace std;
 
void replaceElements(int arr[], int n)
{
    unordered_set<int> s;
 
    for (int i = 0; i < n; i++) {
 
        // check whether the element is
        // repeated or not
        if (s.find(arr[i]) == s.end())
            s.insert(arr[i]);
 
        else {
 
            // find the next greatest element
            for (int j = arr[i] + 1; j < INT_MAX; j++) {
                if (s.find(j) == s.end()) {
                    arr[i] = j;
                    s.insert(j);
                    break;
                }
            }
        }
    }
}
 
int main()
{
    int arr[] = { 1, 2, 5, 7, 8, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    replaceElements(arr, n);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << "\n";
}

// Java program to replace every repeating
// element with next greater element.
import java.util.HashSet;
import java.util.Set;
 
public class ReplaceDuplicateWithGreaterThanPreviousDuplicate {
 
    private static void replaceElements(int[] arr, int n)
    {
        Set<Integer> st = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // check whether the element is
            // repeated or not
            if (!st.contains(arr[i])) {
                st.add(arr[i]);
            }
            else {
                // find the next greatest element
                for (int j = arr[i] + 1; j < Integer.MAX_VALUE; j++) {
                    if (!st.contains(j)) {
                        arr[i] = j;
                        st.add(j);
                        break;
                    }
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int[] arr = new int[] { 1, 2, 5, 7, 8, 8, 7 };
        int n = arr.length;
        replaceElements(arr, n);
 
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

# Python3 program to replace every repeating
# element with next greater element.
import sys
 
def replaceElements(arr, n):
 
    s = []
 
    for i in range (n):
 
        # check whether the element
        # is repeated or not
        if arr[i] not in s:
            s.append(arr[i])
 
        else :
 
            # find the next greatest element
            for j in range(arr[i] + 1, sys.maxsize) :
                if j not in s:
                    arr[i] = j
                    s.append(j)
                    break
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 5, 7, 8, 8, 7 ]
    n = len(arr)
 
    replaceElements(arr, n)
 
    for i in range(n):
        print (arr[i], end = " ")
    print ()
 
# This code is contributed
# by ChitraNayal

// C# program to replace every repeating
// element with next greater element.
using System;
using System.Collections.Generic;
 
public class ReplaceDuplicateWithGreaterThanPreviousDuplicate
{
    private static void replaceElements(int[] arr, int n)
    {
        HashSet<int> st = new HashSet<int>();
        for (int i = 0; i < n; i++)
        {
            // check whether the element is
            // repeated or not
            if (!st.Contains(arr[i]))
            {
                st.Add(arr[i]);
            }
            else
            {
                // find the next greatest element
                for (int j = arr[i] + 1; j < int.MaxValue; j++)
                {
                    if (!st.Contains(j))
                    {
                        arr[i] = j;
                        st.Add(j);
                        break;
                    }
                }
            }
        }
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = new int[] { 1, 2, 5, 7, 8, 8, 7 };
        int n = arr.Length;
        replaceElements(arr, n);
 
        for (int i = 0; i < n; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to replace every repeating
// element with next greater element.
     
    function replaceElements(arr,n)
    {
        let st = new Set();
        for (let i = 0; i < n; i++) {
            // check whether the element is
            // repeated or not
            if (!st.has(arr[i])) {
                st.add(arr[i]);
            }
            else {
                // find the next greatest element
                for (let j = arr[i] + 1; j < Number.MAX_VALUE; j++) {
                    if (!st.has(j)) {
                        arr[i] = j;
                        st.add(j);
                        break;
                    }
                }
            }
        }
    }
     
    let arr=[1, 2, 5, 7, 8, 8, 7];
    let n = arr.length;
    replaceElements(arr, n);
   
    for (let i = 0; i < n; i++) {
        document.write(arr[i] + " ");
    }
     
       
 
 
// This code is contributed by avanitrachhadiya2155
</script>

1 2 5 7 8 9 10