Reemplazo mínimo de pares por su LCM requerido para reducir la array dada a su LCM

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número mínimo de pares (arr[i], arr[j]) de la array dada que se necesita reemplazar con su MCM de modo que la array se reduzca a un solo elemento igual al LCM de la array inicial.
Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4} 
Salida: 3 
Explicación: 
MCM de la array = 12 
Paso 1: MCM(3, 4) = 12. Por lo tanto, la array se modifica a {1, 2, 12} 
Paso 2: LCM(1, 12) = 12. Por lo tanto, el arreglo se modifica a {2, 12} 
Paso 3: LCM(2, 12) = 12. Por lo tanto, el arreglo se modifica a {12}
Entrada: arr[] = {7 , 9, 3} 
Salida: 2 
Explicación: 
LCM del arreglo = 63 
Paso 1: LCM(7, 9) = 63. Por lo tanto el arreglo se modifica a {63, 3} 
Paso 2: LCM(63, 3) = 63. Por lo tanto, la array se modifica a {63} 
 

Enfoque ingenuo: la idea es generar todos los pares posibles y, para cada par, reemplazarlos por su LCM y calcular la cantidad de pasos necesarios para reducirlos a un solo elemento de array igual a su LCM. Imprime el número mínimo de operaciones requeridas.
Complejidad de tiempo: O((N!)*log N) 
Espacio auxiliar: O(N) 

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones: 

  • El MCM de un arreglo es igual al producto de todos los números primos del arreglo.
  • En (X – 1) pasos, el MCM de todos los X números primos se puede obtener usando dos números como pares.
  • En los siguientes (N – 2) pasos, convierta el resto (N – 2) elementos iguales al LCM de la array.
  • Por lo tanto, el número total de pasos viene dado por: 
     

(N – 2) + (X – 1) para N > 2 
 

  • Para N = 1 , el número de operaciones es simplemente 0 y para N = 2 , el número de operaciones es 1 .

Pasos:  

  1. Si N = 1, entonces el conteo de pasos es 0 .
  2. Si N = 2, entonces el conteo de pasos es 1 .
  3. Genere todos los primos hasta N usando Sieve Of Eratosthenes .
  4. Almacene el conteo de números primos en una variable, digamos X .
  5. El conteo total de operaciones viene dado por: 
     

(N – 2) + (X – 1) para N > 2  

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int maxm = 10001;
 
// Boolean array to set or unset
// prime non-prime indices
bool prime[maxm];
 
// Stores the prefix sum of the count
// of prime numbers
int prime_number[maxm];
 
// Function to check if a number
// is prime or not from 0 to N
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p < maxm; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Set its multiples as
            // non-prime
            for (int i = p * p; i < maxm;
                i += p)
                prime[i] = false;
        }
    }
 
    prime[0] = false;
    prime[1] = false;
}
 
// Function to store the count of
// prime numbers
void num_prime()
{
    prime_number[0] = 0;
 
    for (int i = 1; i <= maxm; i++)
 
        prime_number[i]
            = prime_number[i - 1]
            + prime[i];
}
 
// Function to count the operations
// to reduce the array to one element
// by replacing each pair with its LCM
void min_steps(int arr[], int n)
{
    // Generating Prime Number
    SieveOfEratosthenes();
 
    num_prime();
 
    // Corner Case
    if (n == 1)
        cout << "0\n";
 
    else if (n == 2)
        cout << "1\n";
 
    else
        cout << prime_number[n] - 1
                    + (n - 2);
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 5, 4, 3, 2, 1 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    min_steps(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
     
static final int maxm = 10001;
 
// Boolean array to set or unset
// prime non-prime indices
static boolean prime[];
 
// Stores the prefix sum of the count
// of prime numbers
static int prime_number[];
 
// Function to check if a number
// is prime or not from 0 to N
static void SieveOfEratosthenes()
{
    Arrays.fill(prime,true);
 
    for(int p = 2; p * p < maxm; p++)
    {
         
        // If p is a prime
        if (prime[p] == true)
        {
             
            // Set its multiples as
            // non-prime
            for(int i = p * p; i < maxm; i += p)
                prime[i] = false;
        }
    }
    prime[0] = false;
    prime[1] = false;
}
 
// Function to store the count of
// prime numbers
static void num_prime()
{
    prime_number[0] = 0;
 
    for(int i = 1; i <= maxm; i++)
    {
        int tmp;
        if(prime[i] == true)
        {
            tmp = 1;
        }
        else
        {
            tmp = 0;
        }
        prime_number[i] = prime_number[i - 1] + tmp;
    }
}
 
// Function to count the operations
// to reduce the array to one element
// by replacing each pair with its LCM
static void min_steps(int arr[], int n)
{
     
    // Generating Prime Number
    SieveOfEratosthenes();
 
    num_prime();
 
    // Corner Case
    if (n == 1)
    {
        System.out.println("0");
    }
    else if (n == 2)
    {
        System.out.println("1");
    }
    else
    {
        System.out.println(prime_number[n] - 1 +
                                        (n - 2));
    }
}
 
// Driver code   
public static void main(String[] args)
{
    prime = new boolean[maxm + 1];
     
    // Stores the prefix sum of the count
    // of prime numbers
    prime_number = new int[maxm + 1];
     
    // Given array arr[]
    int arr[] = { 5, 4, 3, 2, 1 };
    int N = arr.length;
     
    // Function call
    min_steps(arr, N);
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program for
# the above approach
maxm = 10001;
 
# Boolean array to set or unset
# prime non-prime indices
prime = [True] * (maxm + 1);
 
# Stores the prefix sum of the count
# of prime numbers
prime_number = [0] * (maxm + 1);
 
# Function to check if a number
# is prime or not from 0 to N
def SieveOfEratosthenes():
 
    for p in range(2, (int(maxm ** 1 / 2))):
 
        # If p is a prime
        if (prime[p] == True):
 
            # Set its multiples as
            # non-prime
            for i in range(p * p, maxm, p):
                prime[i] = False;
 
    prime[0] = False;
    prime[1] = False;
 
# Function to store the count of
# prime numbers
def num_prime():
    prime_number[0] = 0;
 
    for i in range(1, maxm + 1):
        tmp = -1;
        if (prime[i] == True):
            tmp = 1;
        else:
            tmp = 0;
 
        prime_number[i] = prime_number[i - 1] + tmp;
 
 
# Function to count the operations
# to reduce the array to one element
# by replacing each pair with its LCM
def min_steps(arr, n):
   
    # Generating Prime Number
    SieveOfEratosthenes();
 
    num_prime();
 
    # Corner Case
    if (n == 1):
        print("0");
    elif (n == 2):
        print("1");
    else:
        print(prime_number[n] - 1 + (n - 2));
 
# Driver code
if __name__ == '__main__':
   
    # Given array arr
    arr = [5, 4, 3, 2, 1];
    N = len(arr);
 
    # Function call
    min_steps(arr, N);
 
# This code is contributed by Rajput-Ji

C#

// C# program for the above approach
using System;
class GFG{
     
static readonly int maxm = 10001;
 
// Boolean array to set or unset
// prime non-prime indices
static bool []prime;
 
// Stores the prefix sum of the count
// of prime numbers
static int []prime_number;
 
// Function to check if a number
// is prime or not from 0 to N
static void SieveOfEratosthenes()
{
    for(int i = 0; i < prime.Length; i++)
        prime[i] = true;
    for(int p = 2; p * p < maxm; p++)
    {       
        // If p is a prime
        if (prime[p] == true)
        {           
            // Set its multiples as
            // non-prime
            for(int i = p * p; i < maxm;
                i += p)
                prime[i] = false;
        }
    }
    prime[0] = false;
    prime[1] = false;
}
 
// Function to store the count of
// prime numbers
static void num_prime()
{
    prime_number[0] = 0;
 
    for(int i = 1; i <= maxm; i++)
    {
        int tmp;
        if(prime[i] == true)
        {
            tmp = 1;
        }
        else
        {
            tmp = 0;
        }
        prime_number[i] = prime_number[i - 1] +
                          tmp;
    }
}
 
// Function to count the operations
// to reduce the array to one element
// by replacing each pair with its LCM
static void min_steps(int []arr, int n)
{   
    // Generating Prime Number
    SieveOfEratosthenes();
 
    num_prime();
 
    // Corner Case
    if (n == 1)
    {
        Console.WriteLine("0");
    }
    else if (n == 2)
    {
        Console.WriteLine("1");
    }
    else
    {
        Console.WriteLine(prime_number[n] - 1 +
                          (n - 2));
    }
}
 
// Driver code   
public static void Main(String[] args)
{
    prime = new bool[maxm + 1];
     
    // Stores the prefix sum of the count
    // of prime numbers
    prime_number = new int[maxm + 1];
     
    // Given array []arr
    int []arr = {5, 4, 3, 2, 1};
    int N = arr.Length;
     
    // Function call
    min_steps(arr, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program for the above approach
     const maxm = 10001;
 
    // Boolean array to set or unset
    // prime non-prime indices
    var prime = Array();
 
    // Stores the prefix sum of the count
    // of prime numbers
    var prime_number = Array();
 
    // Function to check if a number
    // is prime or not from 0 to N
    function SieveOfEratosthenes()
    {
        for(i = 0; i < maxm; i++)
        prime[i] = true;
        for (p = 2; p * p < maxm; p++)
        {
 
            // If p is a prime
            if (prime[p] == true)
            {
 
                // Set its multiples as
                // non-prime
                for (i = p * p; i < maxm; i += p)
                    prime[i] = false;
            }
        }
        prime[0] = false;
        prime[1] = false;
    }
 
    // Function to store the count of
    // prime numbers
    function num_prime() {
        prime_number[0] = 0;
 
        for (i = 1; i <= maxm; i++) {
            var tmp;
            if (prime[i] == true) {
                tmp = 1;
            } else {
                tmp = 0;
            }
            prime_number[i] = prime_number[i - 1] + tmp;
        }
    }
 
    // Function to count the operations
    // to reduce the array to one element
    // by replacing each pair with its LCM
    function min_steps(arr , n) {
 
        // Generating Prime Number
        SieveOfEratosthenes();
 
        num_prime();
 
        // Corner Case
        if (n == 1) {
            document.write("0");
        } else if (n == 2) {
            document.write("1");
        } else {
            document.write(prime_number[n] - 1 + (n - 2));
        }
    }
 
    // Driver code
     
        // Stores the prefix sum of the count
        // of prime numbers
        prime_number.fill(0);
 
        // Given array arr
        var arr = [ 5, 4, 3, 2, 1 ];
        var N = arr.length;
 
        // Function call
        min_steps(arr, N);
 
// This code is contributed by aashish1995
</script>
Producción: 

5

 

Complejidad de tiempo: O(N + log(log(maxm)) 
Espacio auxiliar: O(maxm) 

Publicación traducida automáticamente

Artículo escrito por vishu2908 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *