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

Решение 1: O(n) время & amp; O(n) пробел

Псевдокод

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

Сложность

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

Реализация

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

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

Решение 2: O(n*log(n)) время & amp; O(1) пробел

Псевдокод

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

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

Сложность

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

Реализация

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

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

Это можно сделать быстро с помощью формулы:

мы можем вычислить максимально возможное число для степени 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();
    }