Найти пару чисел с 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

Это можно сделать быстро, используя формулу:

мы можем вычислить максимально возможное число для степени 4, это начало,чтобы минимизировать цикл for, мы можем закончить, когда находимся на половине числа.Решение поддерживает и другие полномочия.Полный код ниже (C #)

public static void Main(string[] args)
    {
        const int raisedPow = 4;
        long num = 3262811042;

        Console.WriteLine("{0}", num);
        int start = (int) Math.Pow(Math.E, (Math.Log(num) / Math.Log(Math.E)) / raisedPow);
        int end = (int) Math.Pow(Math.E, (Math.Log(num/2) / Math.Log(Math.E)) / raisedPow);
        int y = -1;
        int stepCount = 0;

        for (int i = start; i>end;i--)
        {
            stepCount++;
            long rest = (long) (num - (Math.Pow(i, raisedPow)));
            int j = (int) Math.Round(Math.Pow(Math.E, (Math.Log(rest) / Math.Log(Math.E)) / raisedPow));
            if (rest - (Math.Pow(j, raisedPow)) == 0)
            {
                Console.WriteLine("{0} {1}", i, j);

                y = j;
            }
        }
        Console.WriteLine("steps {0}", stepCount);
        if (y == -1) Console.WriteLine("No Solution");

        Console.ReadKey();
    }

Answer 2

Решение 1: O(n) время & O(n) пространство

псевдокод

1. Инициализация хеш-таблицы с предварительно вычисленными значениями : Для каждого элемента x, сохранить в хеш-таблице x^4
2. Поиск пар : Для каждого элемента x, проверьте, есть ли val-x^4 в хеш-таблице

Если шаг 2 находит совпадение, то существует пара, удовлетворяющая требованию.

Сложность

Сложность составляет O(n) для построения хеш-таблицы и O(n) для сканирования. Дополнительно требуется дополнительное пространство O(n).

Осуществление

Для реализации c можно использовать unordered_set.

• Для простоты предполагается, что все значения являются уникальными. Если это не гарантировано, требуется подсчет значений (во избежание x^4+x^4=val, когда x появляется только один раз на входе).

Решение 2: O(n*log(n)) время & O(1) пространство

псевдокод

1. Сортировка всех входных значений по месту : сортировка значений массива в порядке возрастания
2. Поиск пар : Для каждого x, двоичный поиск для sqrt(val-x^4)

Если шаг 2 находит совпадение, то существует пара, которая удовлетворяет требованию.

Comlpexity

Сложность сортировки O(n*log(n)). Каждый бинарный поиск требует O(log(n)) времени и выполняется n раз. Следовательно, общая сложность времени составляет O(n*log(n))

Осуществление

Для реализации c можно использовать qsort.

Answer 3

#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 ^th некоторого числа, ближайшего к sum.
• Теперь, используя подход с двумя указателями (left и right, где right - верхний предел функции бинарного поиска), найдите пару, чьи 4 ^th полномочия складываютсяна данную сумму.Если сумма превышает, мы уменьшаем указатель right, а если он меньше указанной суммы, увеличиваем указатель left.
• Сложность пространства составляет O (1) .

Answer 4

Простая эвристика проверяет значения, меньшие или равные sqrt(sqrt(n)) для входа n. Следовательно, сложность этого алгоритма будет "choose 2 from sqrt(sqrt(n))" = O(sqrt(n)).