C++程序 找到一个数的幂乘积等于另一个数
给定一个长度为 n 的数组 A[] 和一个正整数 k(k > 1),现在您需要找到数量为 Ai,Aj 的数对,使得: **Ai = Aj*(k x ) ** 其中x是整数。
注意:(Ai,Aj)和(Aj,Ai)必须计数一次。
例:
输入:A[] = {3, 6, 4, 2},k = 2
输出:2
解释:我们只有两个数对(4、2)和(3、6)
输入:A[] = {2,2,2} ,k = 2
输出:3
解释:(2,2),(2,2),(2,2)
即(A1,A2),(A2,A3)和(A1,A3)是共三个总数的数对,其中Ai = Aj *(k ^ 0)
要解决这个问题,我们首先对给定的数组进行排序,然后对于每个元素Ai,我们找到等于值Ai*k^x
的元素数,不同的x的值,直到Ai*k^x
小于等于Ai中最大的值。
算法:
// sort the given array
sort(A, A+n);
// for each A[i] traverse rest array
for (i = 0 to n-1)
{
for (j = i+1 to n-1)
{
// count Aj such that Ai*k^x = Aj
int x = 0;
// increase x till Ai * k^x lesser than
// 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;
// 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;
}
结果:
6
时间复杂度: O(n ^ 2),使用嵌套循环
辅助空间: O(1),不使用额外空间