Array with GCD of any of its subset belongs to the given array | Python 3 implementation to generate the required array ; Function to find gcd of array of numbers ; Function to generate the array with required constraints . ; computing GCD of the given set ; Solution exists if GCD of array is equal to the minimum element of the array ; Printing the built array ; Driver function ; 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 ; Calling the computing function .
from math import gcd NEW_LINE def findGCD ( arr , n ) : NEW_LINE INDENT result = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT result = gcd ( arr [ i ] , result ) NEW_LINE DEDENT return result NEW_LINE DEDENT def compute ( arr , n ) : NEW_LINE INDENT answer = [ ] NEW_LINE GCD_of_array = findGCD ( arr , n ) NEW_LINE if ( GCD_of_array == arr [ 0 ] ) : NEW_LINE INDENT answer . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT answer . append ( arr [ 0 ] ) NEW_LINE answer . append ( arr [ i ] ) NEW_LINE DEDENT for i in range ( len ( answer ) ) : NEW_LINE INDENT print ( answer [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " No ▁ array ▁ can ▁ be ▁ build " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 3 NEW_LINE input = [ 2 , 5 , 6 , 7 , 11 ] NEW_LINE GCD = set ( ) NEW_LINE for i in range ( len ( input ) ) : NEW_LINE INDENT GCD . add ( input [ i ] ) NEW_LINE DEDENT arr = [ ] NEW_LINE for i in GCD : NEW_LINE INDENT arr . append ( i ) NEW_LINE DEDENT compute ( arr , n ) NEW_LINE DEDENT