Given an array arr[] consisting of N integers and an integer X, the task is to check if it is possible to modify the array such that the array does not contain any common divisor other than 1, by repeatedly dividing any array element of the array by any of its divisor d (d ≤ X). If it is possible to modify the array such that it satisfies the given conditions, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {6, 15, 6}, X = 6
Output:
Yes
2 5 2
Explanation:
Operation 1: Dividing arr[0] by 3 (Since 3 ≤ 6) modifies arr[] to { 2, 15, 6 }.
Operation 2: Dividing arr[1] by 5 (Since 5 ≤ 6) modifies arr[] to { 2, 3, 6 }.
Therefore, GCD of the array = GCD({2, 3, 6}) = 1, which means that the array has no common divisor other than 1, which is the required condition.Input: arr[] = {10, 20, 30}, X = 4
Output: No
Approach: The idea is to use Euclidean’s GCD to find the GCD of the given array. This gives all the common factors of array elements. By removing all these factors, no common factor remains. Therefore, such an array can be generated. Otherwise, it is not possible to generate such an array.
Follow the steps below to solve the problem:
- Initialize a variable, say G, to store the GCD of the given array.
- Traverse the array arr[] and compute the GCD and store it in a variable, say G.
- Iterate over the range [2, X] and check whether G has a divisor greater than X or not.
- If found to be true, then print “No”. Otherwise, print “Yes”.
- Otherwise, print the array elements after modifying the array by dividing all elements by G.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to modify the array such that// there is no common factor between// array elements except 1void checkCommonDivisor(int arr[], int N, int X){ // Stores GCD of the array int G = 0; // Calculate GCD of the array for (int i = 0; i < N; i++) { G = __gcd(G, arr[i]); } int copy_G = G; for (int divisor = 2; divisor <= X; divisor++) { // If the current divisor // is smaller than X while (G % divisor == 0) { // Divide GCD by the // current divisor G = G / divisor; } } // If possible if (G <= X) { cout << "Yes\n"; // Print the modified array for (int i = 0; i < N; i++) cout << arr[i] / copy_G << " "; cout << endl; } // Otherwise else cout << "No";}// Driver Codeint main(){ // Given array int arr[] = { 6, 15, 6 }, X = 6; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); checkCommonDivisor(arr, N, X);} |
Java
// Java program for the above approachclass GFG{// Function to check if it is possible// to modify the array such that// there is no common factor between// array elements except 1static void checkCommonDivisor(int[] arr, int N, int X){ // Stores GCD of the array int G = 0; // Calculate GCD of the array for(int i = 0; i < N; i++) { G = gcd(G, arr[i]); } int copy_G = G; for(int divisor = 2; divisor <= X; divisor++) { // If the current divisor // is smaller than X while (G % divisor == 0) { // Divide GCD by the // current divisor G = G / divisor; } } // If possible if (G <= X) { System.out.println("Yes"); // Print the modified array for(int i = 0; i < N; i++) System.out.print((arr[i] / copy_G) + " "); System.out.println(); } // Otherwise else System.out.println("No");}// Calculating gcdstatic int gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// Driver Codepublic static void main(String[] args){ int[] arr = { 6, 15, 6 }; int X = 6; // Size of the array int N = arr.length; checkCommonDivisor(arr, N, X);}}// This code is contributed by user_qa7r |
Python3
# Python3 program for the above approachimport math# Function to check if it is possible# to modify the array such that# there is no common factor between# array elements except 1def checkCommonDivisor(arr, N, X): # Stores GCD of the array G = 0 # Calculate GCD of the array for i in range(N): G = math.gcd(G, arr[i]) copy_G = G for divisor in range(2, X + 1): # If the current divisor # is smaller than X while (G % divisor == 0): # Divide GCD by the # current divisor G = G // divisor # If possible if (G <= X): print("Yes") # Print the modified array for i in range(N): print(arr[i] // copy_G, end = " ") print() # Otherwise else: print("No")# Driver Codeif __name__ == "__main__": # Given array arr = [6, 15, 6] X = 6 # Size of the array N = len(arr) checkCommonDivisor(arr, N, X)# This code is contributed by ukasp |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static int GCD(int a, int b){ return b == 0 ? a : GCD(b, a % b);} // Function to check if it is possible// to modify the array such that// there is no common factor between// array elements except 1static void checkCommonDivisor(int []arr, int N, int X){ // Stores GCD of the array int G = 0; // Calculate GCD of the array for(int i = 0; i < N; i++) { G = GCD(G, arr[i]); } int copy_G = G; for(int divisor = 2; divisor <= X; divisor++) { // If the current divisor // is smaller than X while (G % divisor == 0) { // Divide GCD by the // current divisor G = G / divisor; } } // If possible if (G <= X) { Console.WriteLine("Yes"); // Print the modified array for(int i = 0; i < N; i++) Console.Write(arr[i] / copy_G + " "); Console.Write("\n"); } // Otherwise else Console.WriteLine("No");}// Driver Codepublic static void Main(){ // Given array int []arr = { 6, 15, 6 }; int X = 6; // Size of the array int N = arr.Length; checkCommonDivisor(arr, N, X);}}// This code is contributed by bgangwar59 |
Javascript
<script>// javascript program for the above approach // Function to check if it is possible // to modify the array such that // there is no common factor between // array elements except 1 function checkCommonDivisor(arr , N , X) { // Stores GCD of the array var G = 0; // Calculate GCD of the array for (i = 0; i < N; i++) { G = gcd(G, arr[i]); } var copy_G = G; for (divisor = 2; divisor <= X; divisor++) { // If the current divisor // is smaller than X while (G % divisor == 0) { // Divide GCD by the // current divisor G = G / divisor; } } // If possible if (G <= X) { document.write("Yes<br/>"); // Print the modified array for (i = 0; i < N; i++) document.write((arr[i] / copy_G) + " "); document.write(); } // Otherwise else document.write("No"); } // Calculating gcd function gcd(a , b) { if (b == 0) return a; return gcd(b, a % b); } // Driver Code var arr = [ 6, 15, 6 ]; var X = 6; // Size of the array var N = arr.length; checkCommonDivisor(arr, N, X);// This code is contributed by todaysgaurav</script> |
Output:
Yes 2 5 2
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
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!
