Se le proporciona una array A[] de n elementos y un entero positivo k (que no sea 1). Ahora tiene que encontrar el número de pares Ai, Aj tales que Ai = Aj*(k x ) donde x es un número entero. Dado que (k≠1) .
Nota: (Ai, Aj) y (Aj, Ai) deben contarse una vez.
Ejemplos:
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)
Para resolver este problema, primero ordenamos la array dada y luego para cada elemento Ai, encontramos un número de elementos igual al valor Ai * k^x para diferentes valores de x hasta que Ai * k^x es menor o igual que el mayor de Ai.
Algoritmo:
// 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;
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>
Producción :
6
Complejidad de tiempo: O(n*n), ya que se utilizan bucles anidados
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA