Smallest subsequence having GCD equal to GCD of given array | Python3 program to implement the above approach ; Function to print the smallest subsequence that satisfies the condition ; Stores gcd of the array . ; Traverse the given array ; Update gcdArr ; Traverse the given array . ; If current element equal to gcd of array . ; Generate all possible pairs . ; If gcd of current pair equal to gcdArr ; Print current pair of the array ; Driver Code
import math NEW_LINE def printSmallSub ( arr , N ) : NEW_LINE INDENT gcdArr = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT gcdArr = math . gcd ( gcdArr , arr [ i ] ) NEW_LINE DEDENT for i in range ( 0 , N ) : NEW_LINE INDENT if ( arr [ i ] == gcdArr ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE return NEW_LINE DEDENT for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( i + 1 , N ) : NEW_LINE INDENT if ( math . gcd ( arr [ i ] , arr [ j ] ) == gcdArr ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE print ( arr [ j ] , end = " ▁ " ) NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 6 , 12 ] NEW_LINE N = len ( arr ) NEW_LINE printSmallSub ( arr , N ) NEW_LINE DEDENT