Given a set of N elements such that N![\in [1, 1000]](https://geeksforgeeks.org/wp-content/uploads/2023/10/neveropen_quicklatex.com-4b3ef97d3eb6e57b459001149910b709_l3.png "Rendered by QuickLaTeX.com")
, task is to generate an array such that the GCD of any subset of the generated array lies in the given set of elements. The generated array should not be more than thrice the length of the set of the GCD.
Prerequisite : GCD of an Array | Subset of Array
Examples :
Input : 3
1 2 7
Output : 1 1 2 1 7
Input : 4
2 4 6 12
Output : 2 2 4 2 6 2 12
Input : 5
2 5 6 7 11
Output : No array can be build
Explanation: Calculate the GCD of an array or in this case a set. Now, first sort the given set of GCD. If the GCD of this set is equal to the minimum number of the given set, then just by putting this GCD between each number. But, if this GCD is not the minimum element of the given set, then unfortunately “no array can be build”.
Implementation:
C++
// C++ implementation to generate the // required array#include <bits/stdc++.h>using namespace std;// Function to return gcd of a and bint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to find gcd of// array of numbersint findGCD(vector<int> arr, int n){ int result = arr[0]; for (int i = 1; i < n; i++) result = gcd(arr[i], result); return result;}// Function to generate the array// with required constraints.void compute(vector<int> arr, int n){ vector<int> answer; // computing GCD of the given set int GCD_of_array = findGCD(arr, n); // Solution exists if GCD of array is equal // to the minimum element of the array if(GCD_of_array == arr[0]) { answer.push_back(arr[0]); for(int i = 1; i < n; i++) { answer.push_back(arr[0]); answer.push_back(arr[i]); } // Printing the built array for (int i = 0; i < answer.size(); i++) cout << answer[i] << " "; } else cout << "No array can be build";}// Driver functionint main(){ // Taking in the input and initializing // the set STL set in cpp has a property // that it maintains the elements in // sorted order, thus we do not need // to sort them externally int n = 3; int input[]= {2, 5, 6, 7, 11}; set<int> GCD(input, input + n); vector<int> arr; set<int>::iterator it; for(it = GCD.begin(); it!= GCD.end(); ++it) arr.push_back(*it); // Calling the computing function. compute(arr,n); return 0;} |
Java
// Java implementation // to generate the // required arrayimport java.io.*;import java.util.*;class GFG{// Function to return// gcd of a and bstatic int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to find gcd // of array of numberspublic static int findGCD(ArrayList<Integer> arr, int n){ int result = arr.get(0); for (int i = 1; i < n; i++) result = gcd(arr.get(i), result); return result;}// Function to generate // the array with required // constraints.public static void compute(ArrayList<Integer> arr, int n){ ArrayList<Integer> answer = new ArrayList<Integer>(); // computing GCD of // the given set int GCD_of_array = findGCD(arr, n); // Solution exists if GCD // of array is equal to the // minimum element of the array if(GCD_of_array == arr.get(0)) { answer.add(arr.get(0)); for(int i = 1; i < n; i++) { answer.add(arr.get(0)); answer.add(arr.get(i)); } // Printing the // built array for (int i = 0; i < answer.size(); i++) System.out.print(answer.get(i) + " "); } else System.out.print("No array " + "can be build");}// Driver Codepublic static void main(String args[]){ // Taking in the input and // initializing the set STL // set in cpp has a property // that it maintains the // elements in sorted order, // thus we do not need to // sort them externally int n = 3; Integer input[]= {2, 5, 6, 7, 11}; HashSet<Integer> GCD = new HashSet<Integer> (Arrays.asList(input)); ArrayList<Integer> arr = new ArrayList<Integer>(); for (int v : GCD) arr.add(v); // Calling the // computing function. compute(arr, n);}}// This code is contributed by// Manish Shaw(manishshaw1) |
Python3
from math import gcd# Python 3 implementation to generate the # required array# Function to find gcd of# array of numbersdef findGCD(arr, n): result = arr[0] for i in range(1,n): result = gcd(arr[i], result) return result# Function to generate the array# with required constraints.def compute(arr, n): answer = [] # computing GCD of the given set GCD_of_array = findGCD(arr, n) # Solution exists if GCD of array is equal # to the minimum element of the array if(GCD_of_array == arr[0]): answer.append(arr[0]) for i in range(1,n): answer.append(arr[0]) answer.append(arr[i]) # Printing the built array for i in range(len(answer)): print(answer[i],end = " ") else: print("No array can be build")# Driver functionif __name__ == '__main__': # Taking in the input and initializing # the set STL set in cpp has a property # that it maintains the elements in # sorted order, thus we do not need # to sort them externally n = 3 input = [2, 5, 6, 7, 11] GCD = set() for i in range(len(input)): GCD.add(input[i]) arr = [] for i in GCD: arr.append(i) # Calling the computing function. compute(arr,n) # This code is contributed by# Surendra_Gangwar |
C#
// C# implementation // to generate the // required arrayusing System;using System.Collections.Generic;class GFG{ // Function to return // gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to find gcd // of array of numbers static int findGCD(List<int> arr, int n) { int result = arr[0]; for (int i = 1; i < n; i++) result = gcd(arr[i], result); return result; } // Function to generate // the array with required // constraints. static void compute(List<int> arr, int n) { List<int> answer = new List<int>(); // computing GCD of // the given set int GCD_of_array = findGCD(arr, n); // Solution exists if GCD // of array is equal to the // minimum element of the array if(GCD_of_array == arr[0]) { answer.Add(arr[0]); for(int i = 1; i < n; i++) { answer.Add(arr[0]); answer.Add(arr[i]); } // Printing the // built array for (int i = 0; i < answer.Count; i++) Console.Write(answer[i] + " "); } else Console.Write("No array " + "can be build"); } // Driver Code static void Main() { // Taking in the input and // initializing the set STL // set in cpp has a property // that it maintains the // elements in sorted order, // thus we do not need to // sort them externally int n = 3; int []input= new int[]{2, 5, 6, 7, 11}; HashSet<int> GCD = new HashSet<int>(input); List<int> arr = new List<int>(); foreach (int b in GCD) arr.Add(b); // Calling the // computing function. compute(arr, n); }}// This code is contributed by// Manish Shaw(manishshaw1) |
Javascript
<script>// javascript implementation // to generate the // required array // Function to return // gcd of a and b function gcd(a , b) { if (a == 0) return b; return gcd(b % a, a); } // Function to find gcd // of array of numbers function findGCD( arr , n) { var result = arr[0]; for (i = 1; i < n; i++) result = gcd(arr[i], result); return result; } // Function to generate // the array with required // constraints. function compute(arr , n) { var answer = new Array(); // computing GCD of // the given set var GCD_of_array = findGCD(arr, n); // Solution exists if GCD // of array is equal to the // minimum element of the array if (GCD_of_array == arr[0]) { answer.add(arr[0]); for (i = 1; i < n; i++) { answer.add(arr[0]); answer.add(arr[i]); } // Printing the // built array for (var i = 0; i < answer.length; i++) document.write(answer[i] + " "); } else document.write("No array " + "can be build"); } // Driver Code // Taking in the input and // initializing the set STL // set in cpp has a property // that it maintains the // elements in sorted order, // thus we do not need to // sort them externally var n = 3; var input = [ 2, 5, 6, 7, 11 ]; // Calling the // computing function. compute(input, n);// This code is contributed by umadevi9616 </script> |
Output
No array can be build
Complexity Analysis:
- Time Complexity : O(nlog(n)), where n is the size of array given.
- Auxiliary Space: O(n)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
This article is contributed by Aarti_Rathi.
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!
