Recuento de pares que tienen LCM pares e impares de una array

Dada una array arr[] de tamaño N , la tarea es contar el número de pares que tienen LCM pares y LCM impares .

Ejemplos:

Entrada: arr[] = {3, 6, 5, 4}
Salida: Par = 5, Impar = 1
Explicación: MCM de (3, 6) es 6, MCM de (3, 5) es 15, MCM de (3 , 4) es 12, MCM de (6, 5) es 30, MCM de (6, 4) es 12, MCM de (5, 4) es 20.
Los pares que tienen MCM par son (3, 6), (3, 4), (6, 5), (6, 4) y (5, 4).
El único par que tiene MCM impar es (3, 5).

Entrada: arr[] = {4, 7, 2, 12}
Salida: Par = 6, Impar = 0
Explicación: Pares que tienen MCM par = (4, 7), (4, 2), (4, 12), ( 7, 2), (7, 12), (2, 12).
Ningún par tiene MCM impar.

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles para obtener todos los pares distintos y, para cada par, calcular su MCM . Si su MCM es par, aumente el conteo de pares. De lo contrario, aumente el recuento de impares. Finalmente, imprima su cuenta por separado. 
Complejidad de tiempo: O((N ² )*log(M)), donde M es el elemento más pequeño de la array Espacio auxiliar: O(1) 

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en el hecho de que el MCM de 2 números es impar si y solo si ambos números son impares . Por lo tanto, encuentre el total de pares impares en la array y para obtener un conteo de pares con MCM par, reste el conteo de pares impares del número total de pares posibles.

Siga los pasos a continuación para resolver el problema:

• Almacene el recuento total de pares en una variable, digamos totalPairs . Inicialice totalPairs como (N*(N – 1))/2 .
• Almacene el recuento de elementos impares en la array en una variable, digamos cnt .
• Almacene el conteo de pares que consisten solo en números impares, en una variable, digamos impar . Por lo tanto, impar = (cnt*(cnt – 1))/2 .
• Después de completar los pasos anteriores, imprima impar como el valor del conteo de pares con MCM impar. Imprime (totalPairs – impar) como el conteo de pares que tienen MCM par.

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 find count of distinct
// pairs having even LCM and odd LCM
void LCMPairs(int arr[], int N)
{
    // Store the total number of pairs
    int total_pairs = (N * (N - 1)) / 2;
 
    // Stores the count of odd
    // numbers in the array
    int odd = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        if (arr[i] & 1)
            odd++;
    }
 
    // Update the count of pairs with odd LCM
    odd = (odd * (odd - 1)) / 2;
 
    // Print the count of required pairs
    cout << "Even = " << total_pairs - odd
         << ", Odd = " << odd;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 6, 5, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    LCMPairs(arr, N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
  
// Function to find count of distinct
// pairs having even LCM and odd LCM
static void LCMPairs(int arr[], int N)
{
   
    // Store the total number of pairs
    int total_pairs = (N * (N - 1)) / 2;
 
    // Stores the count of odd
    // numbers in the array
    int odd = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
        if ((arr[i] & 1) != 0)
            odd++;
    }
 
    // Update the count of pairs with odd LCM
    odd = (odd * (odd - 1)) / 2;
 
    // Print the count of required pairs
    System.out.println("Even = " +
                       (total_pairs - odd)  +
                       ", Odd = " + odd);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 3, 6, 5, 4 };
    int N = arr.length;
    LCMPairs(arr, N);
}
}
  
// This code is contributed by splevel62.

# Python 3 program for the above approach
 
# Function to find count of distinct
# pairs having even LCM and odd LCM
def LCMPairs(arr, N):
    # Store the total number of pairs
    total_pairs = (N * (N - 1)) / 2
 
    # Stores the count of odd
    # numbers in the array
    odd = 0
 
    # Traverse the array arr[]
    for i in range(N):
        if (arr[i] & 1):
            odd += 1
 
    # Update the count of pairs with odd LCM
    odd = (odd * (odd - 1)) // 2
 
    # Print the count of required pairs
    print("Even =",int(total_pairs - odd),","," Odd =",odd)
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 6, 5, 4]
    N = len(arr)
    LCMPairs(arr, N)
 
     # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find count of distinct
  // pairs having even LCM and odd LCM
  static void LCMPairs(int[] arr, int N)
  {
    // Store the total number of pairs
    int total_pairs = (N * (N - 1)) / 2;
 
    // Stores the count of odd
    // numbers in the array
    int odd = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
      if ((arr[i] & 1) != 0)
        odd++;
    }
 
    // Update the count of pairs with odd LCM
    odd = (odd * (odd - 1)) / 2;
 
    // Print the count of required pairs
    Console.Write("Even = " + (total_pairs - odd) + ", Odd = " + odd);
  }
 
  // Driver code
  static void Main()
  {
    int[] arr = { 3, 6, 5, 4 };
    int N = arr.Length;
    LCMPairs(arr, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// javascript program to implement
// the above approach
 
    // Function to find count of distinct
    // pairs having even LCM and odd LCM
    function LCMPairs(arr , N) {
 
        // Store the total number of pairs
        var total_pairs = (N * (N - 1)) / 2;
 
        // Stores the count of odd
        // numbers in the array
        var odd = 0;
 
        // Traverse the array arr
        for (i = 0; i < N; i++) {
            if ((arr[i] & 1) != 0)
                odd++;
        }
 
        // Update the count of pairs with odd LCM
        odd = (odd * (odd - 1)) / 2;
 
        // Print the count of required pairs
        document.write("Even = " + (total_pairs - odd) + ", Odd = " + odd);
    }
 
    // Driver Code
     
        var arr = [ 3, 6, 5, 4 ];
        var N = arr.length;
        LCMPairs(arr, N);
 
// This code contributed by aashish1995
</script>

Even = 5, Odd = 1

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