Given an array arr[] consisting of N positive integers, the task is to find the minimum number of pairs (arr[i], arr[j]) from the given array needed to be replaced with their LCM such that the array is reduced to a single element equal to the LCM of the initial array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 3
Explanation:
LCM of the array = 12
Step 1: LCM(3, 4) = 12. Therefore array is modified to {1, 2, 12}
Step 2: LCM(1, 12) = 12. Therefore array is modified to {2, 12}
Step 3: LCM(2, 12) = 12. Therefore array is modified to {12}
Input: arr[] = {7, 9, 3}
Output: 2
Explanation:
LCM of the array = 63
Step 1: LCM(7, 9) = 63. Therefore array is modified to {63, 3}
Step 2: LCM(63, 3) = 63. Therefore array is modified to {63}
Naive Approach: The idea is to generate all possible pairs and for each pair, replace them by their LCM and calculate the number of steps required to reduce them to a single array element equal to their LCM. Print the minimum number of operations required.
Time Complexity: O((N!)*log N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the following observations:
- The LCM of an array is equal to the product of all prime numbers in the array.
- In (X – 1) steps, the LCM of all the X prime numbers can be obtained using two numbers as pairs.
- In next (N – 2) steps convert the rest (N – 2) elements equals to the LCM of the array.
- Therefore, the total number of steps is given by:
(N – 2) + (X – 1) for N > 2
- For N = 1, the number of operations is simply 0 and for N = 2, the number of operations is 1.
Steps:
- If N = 1 then the count of steps is 0.
- If N = 2 then the count of steps is 1.
- Generate all primes up to N using Sieve Of Eratosthenes.
- Store the count of primes in a variable, say X.
- The total count of operations is given by:
(N – 2) + (X – 1) for N > 2
Below is the implementation of the above approach:
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 indicesstatic boolean prime[];// Stores the prefix sum of the count// of prime numbersstatic int prime_number[];// Function to check if a number// is prime or not from 0 to Nstatic 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 numbersstatic 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 LCMstatic 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 approachmaxm = 10001;# Boolean array to set or unset# prime non-prime indicesprime = [True] * (maxm + 1);# Stores the prefix sum of the count# of prime numbersprime_number = [0] * (maxm + 1);# Function to check if a number# is prime or not from 0 to Ndef 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 numbersdef 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 LCMdef 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 codeif __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 indicesstatic bool []prime;// Stores the prefix sum of the count// of prime numbersstatic int []prime_number;// Function to check if a number// is prime or not from 0 to Nstatic 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 numbersstatic 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 LCMstatic 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> |
Output:
5
Time Complexity: O(N + log(log(maxm))
Auxiliary Space: O(maxm)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
