You are given an array A[] of N integers. Your task is to make all the elements of the final array equal to 1. You can perform the below operation any number of times (possibly zero). Choose two indices <i, j>, (0<=i,j<N) and replace Ai and Aj both with the GCD ( Greatest Common Divisor ) of Ai and Aj.
Example :
Input : A[] = {2 , 4 , 6 ,9}
Output: Yes
Explanation: First choose 4 and 9 their GCD will be 1, so now the array is {2, 1, 6, 1}. Now, we can choose 2 and 1, their GCD is 1 so, the array becomes {1,1,6,1}. Finally we can choose any 1 with 6 as their GCD is 1. Thus the final array becomes {1, 1, 1, 1}. So, we can make all the array elements equal to 1.
Input : A[] = {9 , 6 , 15}
Output: No
Naive Approach:
- If we get the GCD of any pair equal to 1, then we can make all array elements 1 by taking that number and 1 one by one.
- So, find any co-prime pair exists or not because the GCD of Co-prime pair is equal to 1.
- If the value of GCD pair is equal to 1, then print “Yes”.
- Else print “No”.
Below is the implementation of the above approach :
Java
// Java program to make all the array elements// equal to one by GCD operationsimport java.io.*;import java.lang.*;import java.util.*;public class Main { // Function that returns whether it is possible or not // to make all the array elements equal to one (1) static boolean possible(int A[]) { int n = A.length; // Check all the possible pairs for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int gcd = gcd(A[i], A[j]); // If the gcd is equal to 1 , return true if (gcd == 1) return true; } } return false; } // Recursive function to return gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver Code public static void main(String[] args) { // Given Array int A[] = { 2, 4, 6, 9 }; boolean answer = possible(A); System.out.println(answer == true ? "Yes" : "No"); }} |
Yes
Time Complexity: O(N^2*log N), where N is the length of an array.
Efficient Approach:
- Calculate the GCD of the whole array.
- If there exists any co-prime pair then their GCD will be 1.
- So after this, any number comes, the GCD will remain 1.
- If at any point in time the GCD becomes 1, then break the loop and print “Yes”.
- If the final value of GCD after the whole iteration is not equal to one, then print “No”.
Below is the implementation of the above approach :
Java
// Java program to make all the array elements// equal to one by GCD operationsimport java.io.*;import java.lang.*;import java.util.*;public class Main { // Function that returns whether it is possible or not // to make all the array elements equal to one (1) static boolean possible(int A[]) { int n = A.length; int gcd = 0; // calculate GCD of the whole array for (int i = 0; i < n; i++) { gcd = gcd(gcd, A[i]); // If the gcd is equal to 1 , return true if (gcd == 1) return true; } return false; } // Recursive function to return gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Driver Code public static void main(String[] args) { // Given Array int A[] = { 2, 4, 6, 9 }; boolean answer = possible(A); System.out.println(answer == true ? "Yes" : "No"); }} |
Yes
Time Complexity: O(N*logM), where N is the length of an array and M is the smallest element of an array.
