Pairs such that one is a power multiple of other | Program to find pairs count ; function to count the required pairs ; sort the given array ; for each A [ i ] traverse rest array ; count Aj such that Ai * k ^ x = Aj ; increase x till Ai * k ^ x <= largest element ; driver program
import math NEW_LINE def countPairs ( A , n , k ) : NEW_LINE INDENT ans = 0 NEW_LINE A . sort ( ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT x = 0 NEW_LINE while ( ( A [ i ] * math . pow ( k , x ) ) <= A [ j ] ) : NEW_LINE INDENT if ( ( A [ i ] * math . pow ( k , x ) ) == A [ j ] ) : NEW_LINE INDENT ans += 1 NEW_LINE break NEW_LINE DEDENT x += 1 NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT A = [ 3 , 8 , 9 , 12 , 18 , 4 , 24 , 2 , 6 ] NEW_LINE n = len ( A ) NEW_LINE k = 3 NEW_LINE print ( countPairs ( A , n , k ) ) NEW_LINE