Maximice la distancia reorganizando todos los duplicados a la misma distancia en el Array dado

Dada una array arr[] de Nnúmeros enteros Organice la array de tal manera que la distancia mínima entre todos los pares de los mismos elementos sea la máxima entre todos los arreglos posibles. La tarea es encontrar este valor máximo.

Ejemplos:

Entrada: arr[] = {1, 1, 2, 3}
Salida: 3
Explicación: Todos los arreglos posibles son: 
{1, 1, 2, 3}, {1, 1, 3, 2}, {1, 2, 1, 3}, {1, 2, 3, 1}, {1, 3, 1, 2}, {1, 3, 2, 1}, {2, 1, 1, 3}, {2, 1  
, 3, 1}, {2, 3, 1, 1}, {3, 1, 1, 2}, {3, 1, 2, 1}, {3, 2, 1, 1}.
Aquí los arreglos {1, 2, 3, 1} y {1, 3, 2, 1} dan la respuesta que es 3.
Como distancia = |(índice del primer 1) – (índice del segundo 1)|

Entrada: arr[] = {1, 2, 1, 2, 9, 10, 9}
Salida: 4
Explicación: Uno de esos arreglos es {2, 9, 1, 10, 2, 9, 1}

Enfoque: El enfoque para resolver este problema se basa en la observación de que los elementos con máxima frecuencia deben tener la mayor distancia posible entre ellos . Siga los pasos que se mencionan a continuación para resolver el problema: 

• Averigüe el o los elementos con la máxima frecuencia.
• Supongamos que m elementos tienen la frecuencia máxima max_freq y luego conquistan m*max_freq posiciones desde las N posiciones. Ahora las posiciones desocupadas son un_pos = N – max_freq*m. 
• Ahora, agrupa los elementos que no tienen frecuencia máxima consecutivamente en el mismo orden y tienen un intervalo igual.
• El mayor intervalo puede estar dado por interval = un_pos / ( max_freq -1) porque cuando todas las ocurrencias de m elementos se colocan equidistantes entre sí, se romperá el arreglo en (max_freq – 1) segmentos.
• Y finalmente agregando m para los elementos de frecuencia más alta, uno para cada uno, obtenemos la respuesta a la pregunta dada como intervalo + m.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// the maximum possible minimum distance
int find_max_distance(vector<int> a, int n)
{
    int m = 0, max_freq = 0;
    int un_pos, interval, answer;
 
    // To count frequency of
    // each integer value of array
    map<int, int> count_freq;
 
    for (int i = 0; i < n; i++) {
        count_freq[a[i]]++;
        max_freq = max(max_freq,
                       count_freq[a[i]]);
    }
 
    // Loop to find the number of integers
    // in array with maximum frequency
    for (auto iterator : count_freq) {
        if (iterator.second == max_freq)
            m++;
    }
 
    un_pos = n - m * max_freq;
    interval = un_pos / (max_freq - 1);
 
    answer = interval + m;
 
    return answer;
}
 
// Driver Code
int main()
{
    int N = 7;
    vector<int> arr = { 1, 2, 1, 2, 9, 10, 9 };
 
    int result = find_max_distance(arr, N);
    cout << result;
    return 0;
}

// JAVA code to implement the above approach
import java.util.*;
class GFG
{
   
  // Function to find
  // the maximum possible minimum distance
  public static int find_max_distance(int[] a, int n)
  {
    int m = 0, max_freq = 0;
    int un_pos, interval, answer;
 
    // To count frequency of
    // each integer value of array
    HashMap<Integer, Integer> count_freq
      = new HashMap<>();
 
    for (int i = 0; i < n; i++) {
      if (count_freq.containsKey(a[i])) {
        count_freq.put(a[i],
                       count_freq.get(a[i]) + 1);
      }
      else {
        count_freq.put(a[i], 1);
      }
      max_freq
        = Math.max(max_freq, count_freq.get(a[i]));
    }
 
    // Loop to find the number of integers
    // in array with maximum frequency
    for (Map.Entry<Integer, Integer> iterator :
         count_freq.entrySet()) {
      if (iterator.getValue() == max_freq)
        m++;
    }
 
    un_pos = n - m * max_freq;
    interval = un_pos / (max_freq - 1);
 
    answer = interval + m;
 
    return answer;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 7;
    int[] arr = new int[] { 1, 2, 1, 2, 9, 10, 9 };
 
    int result = find_max_distance(arr, N);
    System.out.print(result);
  }
}
 
// This code is contributed by Taranpreet

# Python code to implement the above approach
# Function to find
# the maximum possible minimum distance
def find_max_distance(a, n):
    m = 0
    max_freq = 0
    un_pos = 0
    interval = 0
    answer = 0
 
    # To count frequency of
    # each integer value of array
    count_freq = {}
 
    for i in range(n):
        if a[i] not in count_freq:
            count_freq[a[i]] = 1
        else:
            count_freq[a[i]] += 1
        max_freq = max(max_freq,count_freq[a[i]])
     
 
    # Loop to find the number of integers
    # in array with maximum frequency
    for i in count_freq:
        if (count_freq[i] == max_freq):
            m += 1
     
    un_pos = n - m * max_freq
    interval = un_pos // (max_freq - 1)
 
    answer = interval + m
 
    return answer
 
# Driver Code
N = 7
arr =  [1, 2, 1, 2, 9, 10, 9]
result = find_max_distance(arr, N)
print(result)
 
# This code is contributed by rohitsingh07052.

// C# code to implement the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find
  // the maximum possible minimum distance
  public static int find_max_distance(int[] a, int n)
  {
    int m = 0, max_freq = 0;
    int un_pos = 0, interval = 0, answer = 0;
 
    // To count frequency of
    // each integer value of array
    Dictionary<int, int> count_freq
      = new Dictionary<int, int>();
 
    for (int i = 0; i < n; i++) {
      if (count_freq.ContainsKey(a[i])) {
        count_freq[a[i]] = count_freq[a[i]] + 1;
      }
      else {
        count_freq.Add(a[i], 1);
      }
      max_freq = Math.Max(max_freq, count_freq[a[i]]);
    }
 
    // Loop to find the number of integers
    // in array with maximum frequency
    foreach(
      KeyValuePair<int, int> iterator in count_freq)
    {
      if (iterator.Value == max_freq)
        m++;
    }
 
    un_pos = n - m * max_freq;
    interval = un_pos / (max_freq - 1);
 
    answer = interval + m;
 
    return answer;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 7;
    int[] arr = new int[] { 1, 2, 1, 2, 9, 10, 9 };
 
    int result = find_max_distance(arr, N);
    Console.Write(result);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the above approach
 
    // Function to find
    // the maximum possible minimum distance
    const find_max_distance = (a, n) => {
        let m = 0, max_freq = 0;
        let un_pos, interval, answer;
 
        // To count frequency of
        // each integer value of array
        let count_freq = {};
 
        for (let i = 0; i < n; i++) {
            if (a[i] in count_freq) count_freq[a[i]]++;
            else count_freq[a[i]] = 1;
            max_freq = Math.max(max_freq,
                count_freq[a[i]]);
        }
 
        // Loop to find the number of integers
        // in array with maximum frequency
        for (let iterator in count_freq) {
            if (count_freq[iterator] == max_freq)
                m++;
        }
 
        un_pos = n - m * max_freq;
        interval = parseInt(un_pos / (max_freq - 1));
        answer = interval + m;
        return answer;
    }
 
    // Driver Code
    let N = 7;
    let arr = [1, 2, 1, 2, 9, 10, 9];
 
    let result = find_max_distance(arr, N);
    document.write(result);
 
// This code is contributed by rakeshsahni
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(N)