Given an array arr[] consisting of N elements, the task is to minimize the array length by replacing any two coprime array elements with 1.
Examples:
Input: arr[] = {2, 3, 5}
Output: 1
Explanation:
Replace {2, 3} with 1 modifies the array to {1, 5}.
Replace {1, 5} with 1 modifies the array to {1}.
Input: arr[] = {6, 9, 15}
Output: 3
Explanation: No coprime pairs exist in the array. Therefore, no reduction possible.
Naive Approach: The simplest approach is to iterate over the array and check for coprime pairs. If found replace it with 1 search for the next coprime pair and so on.
Time Complexity: O(N3 * log N)
Auxiliary Space: O(1)
Efficient Approach: This approach is based on the fact:
1 is coprime with every number
The idea is to find if there is any co-prime pair present in the array or not. If found, then all the array elements can be reduced to 1 based on the above fact. Hence, if any co-prime pair is found, then, the required answer will be 1, else, the answer will be the initial size of the array.
Illustration:
For arr[] = {2, 4, 6, 8, 9}
Here, as there exists a coprime pair {2, 9}, replacing them by 1 modifies the array to {1, 4, 6, 8}.
Since 1 is coprime with every number, the array can be reduced further in following steps:
{1, 4, 6, 8} -> {1, 6, 8} -> {1, 8} -> {1}
Hence, the array can be reduced to size 1.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the final array// length by replacing coprime pair with 1bool hasCoprimePair(vector<int>& arr, int n){ // Iterate over all pairs of element for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Check if gcd is 1 if (__gcd(arr[i], arr[j]) == 1) { return true; } } } // If no coprime pair // found return false return false;}// Driver codeint main(){ int n = 3; vector<int> arr = { 6, 9, 15 }; // Check if atleast one coprime // pair exists in the array if (hasCoprimePair(arr, n)) { cout << 1 << endl; } // If no such pair exists else { cout << n << endl; }} |
Java
// Java Program for the above approachimport java.util.*;class GFG{ // Recursive function to return// gcd of a and b static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }// Function to find the final array// length by replacing coprime pair with 1static boolean hasCoprimePair(int []arr, int n){ // Iterate over all pairs of element for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Check if gcd is 1 if ((__gcd(arr[i], arr[j])) == 1) { return true; } } } // If no coprime pair // found return false return false;}// Driver codepublic static void main(String[] args){ int n = 3; int []arr = { 6, 9, 15 }; // Check if atleast one coprime // pair exists in the array if (hasCoprimePair(arr, n)) { System.out.print(1 + "\n"); } // If no such pair exists else { System.out.print(n + "\n"); }}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approachimport math# Function to find the final array# length by replacing coprime pair with 1def hasCoprimePair(arr, n): # Iterate over all pairs of element for i in range(n - 1): for j in range(i + 1, n): # Check if gcd is 1 if (math.gcd(arr[i], arr[j]) == 1): return True # If no coprime pair # found return false return False# Driver codeif __name__ == "__main__": n = 3 arr = [ 6, 9, 15 ] # Check if atleast one coprime # pair exists in the array if (hasCoprimePair(arr, n)): print(1) # If no such pair exists else: print(n) # This code is contributed by chitranayal |
C#
// C# Program for the above approachusing System;class GFG{ // Recursive function to return// gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); }// Function to find the readonly array// length by replacing coprime pair with 1static bool hasCoprimePair(int []arr, int n){ // Iterate over all pairs of element for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Check if gcd is 1 if ((__gcd(arr[i], arr[j])) == 1) { return true; } } } // If no coprime pair // found return false return false;}// Driver codepublic static void Main(String[] args){ int n = 3; int []arr = { 6, 9, 15 }; // Check if atleast one coprime // pair exists in the array if (hasCoprimePair(arr, n)) { Console.Write(1 + "\n"); } // If no such pair exists else { Console.Write(n + "\n"); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript Program for the above approach // Recursive function to return // gcd of a and b function __gcd(a , b) { return b == 0 ? a : __gcd(b, a % b); } // Function to find the final array // length by replacing coprime pair with 1 function hasCoprimePair(arr , n) { // Iterate over all pairs of element for (i = 0; i < n - 1; i++) { for (j = i + 1; j < n; j++) { // Check if gcd is 1 if ((__gcd(arr[i], arr[j])) == 1) { return true; } } } // If no coprime pair // found return false return false; } // Driver code var n = 3; var arr = [ 6, 9, 15 ]; // Check if atleast one coprime // pair exists in the array if (hasCoprimePair(arr, n)) { document.write(1 + "\n"); } // If no such pair exists else { document.write(n + "\n"); }// This code contributed by gauravrajput1</script> |
3
Time Complexity: O(N2 * log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
