c - 找到一对数字的4次方等于输入数字

Question

接收一个输入数字，找到一个有效的算法来查找是否存在一个和 等于该数字的 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 的幂将提供小于请求输入的数字，并检查所有可能数字的总和是否与此匹配数量。

看起来效率不是很高。请问，你能帮忙吗？谢谢

Answer 1

#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 是二分查找函数的上限)，找到该对其 4^th 次方相加等于给定的总和。如果总和超过，则递减 right 指针，如果小于给定总和，则递增 left 指针。
• 空间复杂度为O(1)。