接收一个输入数字,找到一个有效的算法来查找是否存在一个和 等于该数字的 4 次方数字对。 例如:
Input: val=337
x=3^4=81
y=4^4=256
81+256=337
另一个例子是:
val=641
x=5^4=625
y=2^4=16
val=x+y=641
我试图使用 C 代码解决这个问题。
我考虑过这个问题,我只是想迭代所有可能的数字,其中 4 的幂将提供小于请求输入的数字,并检查所有可能数字的总和是否与此匹配数量。
看起来效率不是很高。 请问,你能帮忙吗? 谢谢
最佳答案
#include<stdio.h>
#include<math.h>
long long int binarySearch(long long int limit){
long long int low = 1,high = sqrt(sqrt(limit));
long long int mid = 0;
long long int ans = 0;
while(low <= high){
mid = low + (high - low) / 2;
long long int raiseToFour = mid * mid * mid * mid;
if(raiseToFour > limit) high = mid - 1;
else if(raiseToFour < limit){
low = mid + 1;
ans = mid;
}else{
ans = mid;
break;
}
}
return ans;
}
int main(void) {
long long int sum = 337;
long long int i;
long long int left = 1, right = binarySearch(sum);
while(left <= right){
long long int leftFourthPower = left * left * left * left;
long long int rightFourthPower = right * right * right * right;
if(leftFourthPower + rightFourthPower == sum){
printf("%lld ^ 4 + %lld ^ 4 = %lld",left,right,sum);
break;
}else if(leftFourthPower + rightFourthPower > sum){
right--;
}else{
left++;
}
}
return 0;
}
它给出:
3 ^ 4 + 4 ^ 4 = 337
- 那么,从
1
到sqrt(sqrt(sum))
进行二分查找,找到 4 次方的数字一些最接近sum
的数字。 - 现在,使用 2 指针方法(
left
和right
,其中right
是二分查找函数的上限),找到该对其 4th 次方相加等于给定的总和。如果总和超过,则递减right
指针,如果小于给定总和,则递增left
指针。 - 空间复杂度为O(1)。
关于c - 找到一对数字的4次方等于输入数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54269857/