We 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:
// Sorting 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++;
}
}
}
// Returning 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;}// Main 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 arrayA.sort((a,b)=>a-b)// for each A[i] traverse rest arrayfor (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
