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*(kx) 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 pairsint 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 programint 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 countimport 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 countimport math# function to count the required pairsdef 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 programA = [3, 8, 9, 12, 18, 4, 24, 2, 6]n = len(A)k = 3print(countPairs(A, n, k))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# program to find pairs countusing 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 pairsfunction countPairs($A, $n, $k) {$ans = 0;// sort the given arraysort($A);// for each A[i] // traverse rest arrayfor ($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 pairsfunction 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 programvar 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 :
6
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
