Pairs such that one is a power multiple of other

0 0 5 minutes read

You are given an array A[] of n-elements and a positive integer k(other than 1). Now you have find the number of pairs Ai, Aj such that Ai = Aj*(k^x) where x is an integer. Given that (k?1).

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; i++)
    {
        for (int j=i+1; j<n; 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;

Implementation:

C++

// Program to find pairs count
#include <bits/stdc++.h>
using namespace std;
 
// function to count the required pairs
int countPairs(int A[], int n, int k) {
  int ans = 0;
  // sort the given array
  sort(A, A + n);
 
  // for each A[i] traverse rest array
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; 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 ans;
}
 
// driver program
int main() {
  int A[] = {3, 8, 9, 12, 18, 4, 24, 2, 6};
  int n = sizeof(A) / sizeof(A[0]);
  int k = 3;
  cout << countPairs(A, n, k);
  return 0;
}

Java

// Java program to find pairs count
import java.io.*;
import java .util.*;
 
class GFG {
     
    // function to count the required pairs
    static int countPairs(int A[], int n, int k) 
    {
        int ans = 0;
         
        // sort the given array
        Arrays.sort(A);
         
        // for each A[i] traverse rest array
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) 
            {
         
                // count Aj such that Ai*k^x = Aj
                int 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++;
                        break;
                    }
                    x++;
                }
            }
        }
        return ans;
    }
     
    // Driver program
    public static void main (String[] args) 
    {
        int A[] = {3, 8, 9, 12, 18, 4, 24, 2, 6};
        int n = A.length;
        int k = 3;
        System.out.println (countPairs(A, n, k));
         
    }
}
 
// This code is contributed by vt_m.

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

C#

// C# program to find pairs count
using System;
 
class GFG {
     
    // function to count the required pairs
    static int countPairs(int []A, int n, int k) 
    {
        int ans = 0;
         
        // sort the given array
        Array.Sort(A);
         
        // for each A[i] traverse rest array
        for (int i = 0; i < n; i++) 
        {
            for (int j = i + 1; j < n; j++) 
            {
         
                // count Aj such that Ai*k^x = Aj
                int 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++;
                        break;
                    }
                    x++;
                }
            }
        }
        return ans;
    }
     
    // Driver program
    public static void Main () 
    {
        int []A = {3, 8, 9, 12, 18, 4, 24, 2, 6};
        int n = A.Length;
        int k = 3;
        Console.WriteLine(countPairs(A, n, k));
         
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find pairs count
 
// function to count
// the required pairs
function countPairs($A, $n, $k) 
{
$ans = 0;
 
// sort the given array
sort($A);
 
// for each A[i] 
// traverse rest array
for ($i = 0; $i < $n; $i++) 
{
    for ($j = $i + 1; $j < $n; $j++) 
    {
 
    // count Aj such that Ai*k^x = Aj
    $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 $ans;
}
 
// Driver Code
 
$A = array(3, 8, 9, 12, 18, 
              4, 24, 2, 6);
$n = count($A);
$k = 3;
echo countPairs($A, $n, $k);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// Javascript Program to find pairs count
 
// function to count the required pairs
function countPairs(A, n, k) {
  var ans = 0;
   
  // sort the given array
  A.sort((a,b)=>a-b)
 
  // for each A[i] traverse rest array
  for (var i = 0; i < n; i++) {
    for (var j = i + 1; j < n; j++) {
 
      // count Aj such that Ai*k^x = Aj
      var 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++;
          break;
        }
        x++;
      }
    }
  }
  return ans;
}
 
// driver program
var A = [3, 8, 9, 12, 18, 4, 24, 2, 6];
var n = A.length;
var k = 3;
document.write( countPairs(A, n, k));
 
// This code is contributed by rutvik_56.
</script>

Output :

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

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!