Count of distinct GCDs among all the non | Python 3 program for the above approach ; Function to calculate the number of distinct GCDs among all non - empty subsequences of an array ; variables to store the largest element in array and the required count ; Map to store whether a number is present in A ; calculate largest number in A and mapping A to Mp ; iterate over all possible values of GCD ; variable to check current GCD ; iterate over all multiples of i ; If j is present in A ; calculate gcd of all encountered multiples of i ; current GCD is possible ; return answer ; Driver code ; Input ; Function calling
from math import gcd NEW_LINE def distinctGCDs ( arr , N ) : NEW_LINE INDENT M = - 1 NEW_LINE ans = 0 NEW_LINE Mp = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT M = max ( M , arr [ i ] ) NEW_LINE Mp [ arr [ i ] ] = 1 NEW_LINE DEDENT for i in range ( 1 , M + 1 , 1 ) : NEW_LINE INDENT currGcd = 0 NEW_LINE for j in range ( i , M + 1 , i ) : NEW_LINE INDENT if ( j in Mp ) : NEW_LINE INDENT currGcd = gcd ( currGcd , j ) NEW_LINE if ( currGcd == i ) : NEW_LINE INDENT ans += 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 11 , 14 , 6 , 12 ] NEW_LINE N = len ( arr ) NEW_LINE print ( distinctGCDs ( arr , N ) ) NEW_LINE DEDENT