Grupos mínimos para dividir la array de modo que la diferencia de valor de cada par y la diferencia de posición sean las mismas

Dada una array arr[] que consta de N enteros, la tarea es dividir la array en el número mínimo de grupos disjuntos, de modo que las diferencias entre cualquier par de elementos en un grupo sean iguales a la diferencia entre sus posiciones en ese grupo.

Ejemplos:

Entrada: arr[] = {30, 32, 44, 31, 45, 32, 31, 33}
Salida: 3
Explicación:
La única forma posible de dividir la array es:

• Primer grupo: {30, 31, 32, 33}
• Segundo grupo: {31, 32}
• Tercer grupo: {44, 45}

Por lo tanto, el número de grupos es 3, que es el número mínimo de grupos en los que se puede dividir la array que cumple las condiciones.

Entrada: arr[] = {1, 5, 3, 1, 7, 7, 9}
Salida: 7

Enfoque ingenuo: el enfoque más simple es dividir la array en K subconjuntos para cada número entero K menor o igual que N , y luego verificar si todos los subconjuntos de la array satisfacen las condiciones dadas o no. Si se determina que es cierto, imprima el tamaño mínimo posible de la partición.

Complejidad de Tiempo: O(N ^{(N + 2)} )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que los elementos de cada grupo se deben ordenar y la diferencia entre los elementos adyacentes debe ser 1 . Siga los pasos a continuación para resolver el problema:

• Ordena la array dada en orden ascendente.
• Inicialice un mapa, digamos mp para almacenar la frecuencia de los elementos de la array .
• Inicialice una variable, digamos contar como 0 para almacenar el recuento del número mínimo de grupos disjuntos formados.
• Recorre la array dada arr[] e incrementa la frecuencia de cada elemento en el mapa mp .
• Recorra la array dada arr[], usando la variable i , y realice los siguientes pasos:
  • Si el conteo de arr[i] en el mapa mp es al menos 1 , y el conteo de (arr[i] – 1) en el mapa mp entonces:
    • Incrementa el valor de count en 1 .
    • Iterar hasta que el conteo de arr[i] en mp sea mayor que 0 y en cada iteración, disminuir mp[arr[i]] en 1 e incrementar arr[i] en 1 .
• Finalmente, después de completar los pasos anteriores, imprima el valor de la cuenta como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to split the array into
// minimum number of disjoint groups
// satisfying the conditions
int numberOfSplit(int arr[], int N)
{
    // Sort the array in ascending order
    sort(arr, arr + N);
 
    // Stores frequency of array elements
    unordered_map<int, int> mp;
 
    // Traverse the array, arr[]
    for (int i = 0; i < N; i++)
        mp[arr[i]]++;
 
    // Stores the number of groups
    int count = 0;
 
    // Traverse the array, arr[]
    for (int i = 0; i < N; i++) {
 
        // If mp[arr[i]] is at least 1
        // and  mp[arr[i]-1] is 0
        if (mp[arr[i]] > 0 && mp[arr[i] - 1] == 0) {
 
            // Increment the count by 1
            count++;
 
            // Iterate until mp[arr[i]]
            // is greater than 0
            while (mp[arr[i]] != 0) {
 
                // Decrement mp[arr[i]]
                // by 1
                mp[arr[i]]--;
 
                // Increment arr[i] by 1
                arr[i]++;
            }
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 30, 32, 44, 31, 45, 32, 31, 33 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << numberOfSplit(arr, N);
 
    return 0;
}

# Python program for the above approach
 
# Function to split the array into
# minimum number of disjoint groups
# satisfying the conditions
def numberOfSplit(arr, N):
 
    # Sort the array in ascending order
    arr.sort()
 
    # Stores frequency of array elements
    mp = {}
 
    # Traverse the array, arr[]
    for i in range(N):
 
        if(arr[i] in mp):
            mp[arr[i]] = mp[arr[i]]+1
        else:
            mp[arr[i]] = 1
 
    # Stores the number of groups
    count = 0
 
    # Traverse the array, arr[]
    for i in range(N):
 
        # If mp[arr[i]] is at least 1
        # and  mp[arr[i]-1] is 0
        if (arr[i] in mp and mp[arr[i]]>0 and ((arr[i] - 1) not in mp or ((arr[i]-1) in mp and mp[arr[i]-1]==0))):
 
            # Increment the count by 1
            count += 1
             
            # Iterate until mp[arr[i]]
            # is greater than 0
            while arr[i] in mp and mp[arr[i]] > 0:
 
                # Decrement mp[arr[i]]
                # by 1
                mp[arr[i]]  = mp[arr[i]] - 1
 
                # Increment arr[i] by 1
                arr[i] += 1
         
 
    # Return the resultant count
    return count
 
# Driver Code
arr = [30, 32, 44, 31, 45, 32, 31, 33]
N = len(arr)
print(numberOfSplit(arr, N))
 
# This code is contributed by shinjanpatra.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to split the array into
// minimum number of disjoint groups
// satisfying the conditions
static int numberOfSplit(int []arr, int N)
{
     
    // Sort the array in ascending order
    Array.Sort(arr);
 
    // Stores frequency of array elements
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
 
    // Traverse the array, arr[]
    for(int i = 0; i < N; i++)
    {
        if (mp.ContainsKey(arr[i]))
            mp[arr[i]] += 1;
        else
            mp.Add(arr[i], 0);
    }
 
    // Stores the number of groups
    int count = 2;
 
    // Traverse the array, arr[]
    for(int i = 0; i < N; i++)
    {
         
        // If mp[arr[i]] is at least 1
        // and  mp[arr[i]-1] is 0
        if (mp[arr[i]] > 0 && mp[arr[i] - 1] == 0)
        {
             
            // Increment the count by 1
            count++;
 
            // Iterate until mp[arr[i]]
            // is greater than 0
            while (mp[arr[i]] != 0)
            {
                 
                // Decrement mp[arr[i]]
                // by 1
                mp[arr[i]]--;
 
                // Increment arr[i] by 1
                arr[i]++;
            }
        }
    }
   
    // Return the resultant count
    return count;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 30, 32, 44, 31,
                  45, 32, 31, 33 };
    int N = arr.Length;
 
    Console.Write(numberOfSplit(arr, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
 
// Javascript program for the above approach
 
// Function to split the array into
// minimum number of disjoint groups
// satisfying the conditions
function numberOfSplit(arr, N)
{
    // Sort the array in ascending order
    arr.sort();
 
    // Stores frequency of array elements
    var mp = new Map();
 
    // Traverse the array, arr[]
    for (var i = 0; i < N; i++)
    {
        if(mp.has(arr[i]))
         mp.set(arr[i], mp.get(arr[i])+1)
        else
         mp.set(arr[i], 1)
    }
 
    // Stores the number of groups
    var count = 0;
 
    // Traverse the array, arr[]
    for (var i = 0; i < N; i++) {
 
        // If mp[arr[i]] is at least 1
        // and  mp[arr[i]-1] is 0
        if (mp.has(arr[i]) && mp.get(arr[i])>0 && (!mp.has(arr[i] - 1) || (mp.has(arr[i]-1) && mp.get(arr[i]-1)==0))) {
 
            // Increment the count by 1
            count++;
             
            // Iterate until mp[arr[i]]
            // is greater than 0
            while (mp.get(arr[i]) > 0) {
 
                // Decrement mp[arr[i]]
                // by 1
                mp.set(arr[i], mp.get(arr[i])-1);
 
                // Increment arr[i] by 1
                arr[i]++;
            }
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
var arr = [30, 32, 44, 31, 45, 32, 31, 33];
var N = arr.length;
document.write(numberOfSplit(arr, N));
 
// This code is contributed by itsok.
</script>

3

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)