Divida la array en un número mínimo de subconjuntos con una diferencia entre cada par superior a 1

Dada una array arr[] de tamaño N , la tarea es dividir la array en un número mínimo de subconjuntos de modo que cada par de elementos en cada subconjunto tenga una diferencia estrictamente mayor que 1.
Nota: Todos los elementos de la array son distintos.

Ejemplos:

Entrada: arr = {5, 10, 6, 50}
Salida: 2
Explicación: 
Las posibles particiones son: {5, 10, 50}, {6}

Entrada: arr = {2, 4, 6}
Salida: 1
Explicación: 
Las posibles particiones son: {2, 4, 6}

Planteamiento: La idea es observar que si no existe tal par i , j tal que |arr[i] – arr[j]| = 1 , entonces es posible poner todos los elementos en la misma partición, de lo contrario dividirlos en dos particiones. Entonces, el número mínimo requerido de particiones es siempre 1 o 2 .

1. Ordenar la array dada.
2. Compara los elementos adyacentes. Si en algún momento su diferencia es igual a 1, imprima «2» , ya que el número requerido de partición de subconjunto siempre será 2, ya que podemos colocar uno de los elementos del par anterior en otro subconjunto.
3. Si atravesamos toda la array y no encontramos ningún par adyacente con una diferencia inferior a 2, imprima «1» sin dividir la array en subconjuntos, podemos tener todos los pares posibles con una diferencia de al menos 2.

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 subsets with
// difference strictly > 1
void split(int arr[], int n)
{
    // Sort the array
    sort(arr, arr + n);
    int count = 1;
 
    // Traverse through the sorted array
    for (int i = 1; i < n; i++) {
 
        // Check the pairs of elements
        // with difference 1
        if (arr[i] - arr[i - 1] == 1) {
 
            // If we find even a single
            // pair with difference equal
            // to 1, then 2 partitions
            // else only 1 partition
            count = 2;
            break;
        }
    }
 
    // Print the count of partitions
    cout << count << endl;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 6 };
 
    // Size of the array
    int n = sizeof(arr) / sizeof(int);
 
    // Function Call
    split(arr, n);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to split the array into
// minimum number of subsets with
// difference strictly > 1
static void split(int arr[], int n)
{
     
    // Sort the array
    Arrays.sort(arr);
    int count = 1;
 
    // Traverse through the sorted array
    for(int i = 1; i < n; i++)
    {
         
        // Check the pairs of elements
        // with difference 1
        if (arr[i] - arr[i - 1] == 1)
        {
             
            // If we find even a single
            // pair with difference equal
            // to 1, then 2 partitions
            // else only 1 partition
            count = 2;
            break;
        }
    }
 
    // Print the count of partitions
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 2, 4, 6 };
 
    // Size of the array
    int n = arr.length;
 
    // Function call
    split(arr, n);
}
}
 
// This code is contributed by jrishabh99

# Python3 implementation of
# the above approach
 
# Function to Split the array into
# minimum number of subsets with
# difference strictly > 1
def split(arr, n):
 
    # Sort the array
    arr.sort()
    count = 1
 
    # Traverse through the sorted array
    for i in range(1, n):
 
        # Check the pairs of elements
        # with difference 1
        if(arr[i] - arr[i - 1] == 1):
 
            # If we find even a single
            # pair with difference equal
            # to 1, then 2 partitions
            # else only 1 partition
            count = 2
            break
 
    # Print the count of partitions
    print(count)
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [ 2, 4, 6 ]
 
    # Size of the array
    n = len(arr)
 
    # Function call
    split(arr, n)
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
class GFG{
      
// Function to split the array into
// minimum number of subsets with
// difference strictly > 1
static void split(int []arr, int n)
{
    // Sort the array
    Array.Sort(arr);
    int count = 1;
  
    // Traverse through the sorted array
    for(int i = 1; i < n; i++)
    {
          
        // Check the pairs of elements
        // with difference 1
        if (arr[i] - arr[i - 1] == 1)
        {
            // If we find even a single
            // pair with difference equal
            // to 1, then 2 partitions
            // else only 1 partition
            count = 2;
            break;
        }
    }
  
    // Print the count of partitions
    Console.Write(count);
}
  
// Driver Code
public static void Main(string[] args)
{
      
    // Given array
    int[] arr = new int[]{ 2, 4, 6 };
  
    // Size of the array
    int n = arr.Length;
  
    // Function call
    split(arr, n);
}
}
  
// This code is contributed by Ritik Bansal

<script>
 
// Javascript program for
// the above approach
 
// Function to split the array into
// minimum number of subsets with
// difference strictly > 1
function split(arr, n)
{
      
    // Sort the array
    arr.sort();
    let count = 1;
  
    // Traverse through the sorted array
    for(let i = 1; i < n; i++)
    {
          
        // Check the pairs of elements
        // with difference 1
        if (arr[i] - arr[i - 1] == 1)
        {
              
            // If we find even a single
            // pair with difference equal
            // to 1, then 2 partitions
            // else only 1 partition
            count = 2;
            break;
        }
    }
  
    // Print the count of partitions
   document.write(count);
}
     
// Driver Code
     
   // Given array
    let arr = [ 2, 4, 6 ];
  
    // Size of the array
    let n = arr.length;
  
    // Function call
    split(arr, n);
 
</script>

1

Complejidad de tiempo: O(N log N), donde N es la longitud de la array.
Espacio Auxiliar: O(1)