Pairs such that one is a power multiple of other | 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 Code
< ? php function countPairs ( $ A , $ n , $ k ) { $ ans = 0 ; sort ( $ A ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { for ( $ j = $ i + 1 ; $ j < $ n ; $ j ++ ) { $ x = 0 ; while ( ( $ A [ $ i ] * pow ( $ k , $ x ) ) <= $ A [ $ j ] ) { if ( ( $ A [ $ i ] * pow ( $ k , $ x ) ) == $ A [ $ j ] ) { $ ans ++ ; break ; } $ x ++ ; } } } return $ ans ; } $ A = array ( 3 , 8 , 9 , 12 , 18 , 4 , 24 , 2 , 6 ) ; $ n = count ( $ A ) ; $ k = 3 ; echo countPairs ( $ A , $ n , $ k ) ; ? >