Python Program for Pairs such that one is a power multiple of other

0 0 2 minutes read

You are given an array A[] of n-elements and a positive integer k (k > 1). Now you have find the number of pairs Ai, Aj such that Ai = Aj*(k^x) where x is an integer.
Note: (Ai, Aj) and (Aj, Ai) must be count once.
Examples :

Input : A[] = {3, 6, 4, 2},  k = 2
Output : 2
Explanation : We have only two pairs 
(4, 2) and (3, 6)

Input : A[] = {2, 2, 2},   k = 2
Output : 3
Explanation : (2, 2), (2, 2), (2, 2) 
that are (A1, A2), (A2, A3) and (A1, A3) are 
total three pairs where Ai = Aj * (k^0)

To solve this problem, we first sort the given array and then for each element Ai, we find number of elements equal to value Ai * k^x for different value of x till Ai * k^x is less than or equal to largest of Ai.
Algorithm:

    // sort the given array
    sort(A, A+n);

    // for each A[i] traverse rest array
    for (int i=0; i ? n-1; i++)
    {
        for (int j=i+1; j ? n-1; j++)
        {
            // count Aj such that Ai*k^x = Aj
            int x = 0;

            // increase x till Ai * k^x ? 
            // largest element
            while ((A[i]*pow(k, x)) ? A[j])
            {
                if ((A[i]*pow(k, x)) == A[j])
                {              
                     ans++;
                     break;
                }
                x++;
            }        
        }   
    }
    // return answer
    return ans;

Python3

# Program to find pairs count
import math
 
# function to count the required pairs
def countPairs(A, n, k): 
    ans = 0
 
    # sort the given array
    A.sort()
     
    # for each A[i] traverse rest array
    for i in range(0,n): 
 
        for j in range(i + 1, n):
 
            # count Aj such that Ai*k^x = Aj
            x = 0
 
            # increase x till Ai * k^x <= largest element
            while ((A[i] * math.pow(k, x)) <= A[j]) :
                if ((A[i] * math.pow(k, x)) == A[j]) :
                    ans+=1
                    break
                x+=1
    return ans
 
 
# driver program
A = [3, 8, 9, 12, 18, 4, 24, 2, 6]
n = len(A)
k = 3
 
print(countPairs(A, n, k))
 
# This code is contributed by
# Smitha Dinesh Semwal

Output :

Time Complexity: O(n*n), as nested loops are used
Auxiliary Space: O(1), as no extra space is used

Please refer complete article on Pairs such that one is a power multiple of other for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!