Divida la array en un número mínimo de subconjuntos de modo que los elementos de todos los pares estén presentes en diferentes subconjuntos al menos una vez

Dada una array arr[] que consta de N enteros distintos, la tarea es encontrar el número mínimo de veces que la array debe dividirse en dos subconjuntos de modo que los elementos de cada par estén presentes en dos subconjuntos diferentes al menos una vez.

Ejemplos:

Entrada: arr[] = { 3, 4, 2, 1, 5 } 
Salida: 3 
Explicación: 
Los pares posibles son { (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5) } 
Dividir la array en { 1, 2 } y { 3, 4 , 5 } 
Los elementos de cada uno de los pares { (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5) } están presentes en dos diferentes subconjuntos. 
Dividir la array en { 1, 3 } y { 2, 4, 5 } 
Elementos de cada uno de los pares { (1, 2) , (1, 4), (1, 5), (2, 3), (3 , 4), (3, 5) } están presentes en dos subconjuntos diferentes. 
Dividir la array en { 1, 3, 4 } y { 2, 5 } 
Elementos de cada uno de los pares { (1, 2), (1, 5), (2, 3), (3, 5), (2 , 4),(4, 5) } están presentes en dos subconjuntos diferentes. 
Dado que los elementos de cada par de la array están presentes en dos subconjuntos diferentes al menos una vez, la salida requerida es 3.

Entrada: arr[] = { 2, 1, 3 } 
Salida: 2 
 

Enfoque: la idea es siempre dividir la array en dos subconjuntos de tamaño floor(N / 2) y ceil(N / 2) . Antes de cada partición, simplemente intercambie el valor de arr[i] con arr[N / 2 + i] . Siga los pasos que se indican a continuación para resolver el problema:

• Si N es impar , entonces el intercambio total posible (arr[i], arr[N/2 + i]) es igual a N/2 + 1 . Por lo tanto, imprima (N / 2 + 1) .
• Si N es par , entonces el intercambio total posible (arr[i], arr[N/2 + i]) es igual a N/2 . Por lo tanto, imprima (N / 2) . 
   

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

// C++ program to to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum count of ways to split
// the array into two subset such that elements of
// each pair occurs in two different subset
int MinimumNoOfWays(int arr[], int n)
{
 
    // Stores minimum count of ways to split array
    // into two subset such that elements of
    // each pair occurs in two different subset
    int mini_no_of_ways;
 
    // If N is odd
    if (n % 2 == 0) {
        mini_no_of_ways = n / 2;
    }
    else {
        mini_no_of_ways = n / 2 + 1;
    }
    return mini_no_of_ways;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 4, 2, 1, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << MinimumNoOfWays(arr, N);
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
   
class GFG{
   
// Function to find minimum count of ways to split
// the array into two subset such that elements of
// each pair occurs in two different subset
static int MinimumNoOfWays(int arr[], int n)
{
  
    // Stores minimum count of ways to split array
    // into two subset such that elements of
    // each pair occurs in two different subset
    int mini_no_of_ways;
  
    // If N is odd
    if (n % 2 == 0) {
        mini_no_of_ways = n / 2;
    }
    else {
        mini_no_of_ways = n / 2 + 1;
    }
    return mini_no_of_ways;
}
   
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 4, 2, 1, 5 };
    int N = arr.length;
    System.out.print(MinimumNoOfWays(arr, N));
}
}
 
// This code is contributed by sanjoy_62

# Python program to to implement
# the above approach
 
# Function to find minimum count of ways to split
# the array into two subset such that elements of
# each pair occurs in two different subset
def MinimumNoOfWays(arr, n):
   
    # Stores minimum count of ways to split array
    # into two subset such that elements of
    # each pair occurs in two different subset
    min_no_of_ways = 0
     
    # if n is even
    if (n % 2 == 0):
        mini_no_of_ways = n // 2
         
    # n is odd
    else:
        mini_no_of_ways = n // 2 + 1
         
    return mini_no_of_ways
 
# driver code
if __name__ == '__main__':
    arr = [3, 4, 1, 2, 5]
    n = len(arr)
    print(MinimumNoOfWays(arr, n))
 
# This code is contributed by MuskanKalra1

// C# program to implement
// the above approach
using System;
class GFG
{
   
// Function to find minimum count of ways to split
// the array into two subset such that elements of
// each pair occurs in two different subset
static int MinimumNoOfWays(int []arr, int n)
{
  
    // Stores minimum count of ways to split array
    // into two subset such that elements of
    // each pair occurs in two different subset
    int mini_no_of_ways;
  
    // If N is odd
    if (n % 2 == 0)
    {
        mini_no_of_ways = n / 2;
    }
    else
    {
        mini_no_of_ways = n / 2 + 1;
    }
    return mini_no_of_ways;
}
   
  // Driver code
  public static void Main(string[] args)
  {
      int[] arr = { 3, 4, 2, 1, 5 };
      int N = arr.Length;
      Console.WriteLine(MinimumNoOfWays(arr, N));
  }
}
 
// This code is contributed by AnkThon

<script>
// javascript program to implement
// the above approach
 
    // Function to find minimum count of ways to split
    // the array into two subset such that elements of
    // each pair occurs in two different subset
    function MinimumNoOfWays(arr , n) {
 
        // Stores minimum count of ways to split array
        // into two subset such that elements of
        // each pair occurs in two different subset
        var mini_no_of_ways;
 
        // If N is odd
        if (n % 2 == 0) {
            mini_no_of_ways = n / 2;
        } else {
            mini_no_of_ways = n / 2 + 1;
        }
        return parseInt(mini_no_of_ways);
    }
 
    // Driver code
     
        var arr = [ 3, 4, 2, 1, 5 ];
        var N = arr.length;
        document.write(MinimumNoOfWays(arr, N));
 
// This code contributed by gauravrajput1
</script>

3

Complejidad de tiempo: O(1)  
Complejidad de espacio: O(1)