Count the number of pairs ( i , j ) such that either arr [ i ] is divisible by arr [ j ] or arr [ j ] is divisible by arr [ i ] | Function to find number of unordered pairs ; Maximum element from the array ; Array to store the frequency of each element ; Stores the number of unordered pairs ; Store the frequency of each element ; Find the number of unordered pairs ; If the number j divisible by ith element is present in the array ; If the ith element of the array has frequency more than one ; Driver code
def freqPairs ( arr , n ) : NEW_LINE INDENT max = arr [ 0 ] NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT if arr [ i ] > max : NEW_LINE INDENT max = arr [ i ] NEW_LINE DEDENT DEDENT freq = [ 0 for i in range ( max + 1 ) ] NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( 2 * arr [ i ] , max + 1 , arr [ i ] ) : NEW_LINE INDENT if ( freq [ j ] >= 1 ) : NEW_LINE INDENT count += freq [ j ] NEW_LINE DEDENT DEDENT if ( freq [ arr [ i ] ] > 1 ) : NEW_LINE INDENT count += freq [ arr [ i ] ] - 1 NEW_LINE freq [ arr [ i ] ] -= 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 2 , 4 , 2 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( freqPairs ( arr , n ) ) NEW_LINE DEDENT