Алгоритм нахождения суммы степеней с уменьшающим основанием

Question

Задача

Решаю задачу на Codewars: найти для следующей формулы n^3 + (n-1)^3 + ... + 1^3 = m число n. Число m известно и передается в функцию FindNb. Если для переданного m не существует n, то ответ: -1. Например:

FindNb(1071225) --> 45

FindNb(91716553919377) --> -1

---

Мое решение

Вот что сделал я:

public static long FindNb(long m)
{            
    long sum = 0;
    var nResult = 0;

    for (var i = 1; sum < m; i++)
    {
        sum = 0;
        nResult = i;
        for (var nMaybe = i; nMaybe > 0; nMaybe--)
        {
            sum += (long)Math.Pow(nMaybe, 3.0);
        }
    }
    if (sum != m)
    {
        nResult = -1;
    }

    return nResult;
}

---

Вопрос

Мое решение работает, но сервис требует оптимизировать код (слишком долго выполняется). Как это сделать?

• сложность моего алгоритма получилась квадратичная (N^2). Не знаю как уменьшить ее.
• также думал может приведение ...(long)Math.Pow... замедляет код, но поиск оптимизации по этой части тоже ничего не дал.

Answer 1

А если попробовать такой вариант, без вложенных циклов:

public static long FindNb1(long m)
{
    var i = 0;
    long sum = 0;
    while (sum < m)
    {
        i++;
        sum = sum + (long)Math.Pow(i, 3.0);
    }

    if(sum != m)
        return -1;

    return i;
}

Дело вот в чём: счёт идёт обратно, от единицы:

при n = 1 мы имеем формулу 1^3

при n = 2 мы имеем формулу 2^3 + 1^3

при n = 3 мы имеем формулу 3^3 + 2^3 + 1^3

и так далее. Накапливаем результат и на каждой итерации смотрим, не проскочили ли мы наш "эталон" в размере m. Если совпали с эталоном -- выводим счётчик цикла, если нет ("перескочили лишку") -- выводим -1.

У меня Stopwatch показывает на 100 повторах кода ускорение на порядок (исходный вариант, оптмизированный):

16386
1309

Answer 2

Реализация идеи из ответа @Harry с формулой S = [n(n+1)/2]^2 и квадратным корнем:

public static long FindNb(long m)
{
    var q = GetSqrtOrMinusOne(m);
    if (q == -1)
        return -1;
    // n(n+1)/2 = q <=> 4n^2 + 4n = 8q <=> 4n^2 + 4n + 1 = 8q + 1 <=> (2n + 1)^2 = 8q + 1
    var r = GetSqrtOrMinusOne(8 * q + 1); // r = 2n + 1
    if (r == -1)
        return -1;
    // 8q + 1 нечётно => r тоже нечётно, проверка не нужна
    return (r - 1) / 2;
}

static long GetSqrtOrMinusOne(long original)
{
    // для чисел в диапазоне long точности хватает, так что можно считать, что
    // ошибка не превосходит 0.5 => используем Math.Round.
    var q = (int)Math.Round(Math.Sqrt(original));
    return (q * q == original) ? q : -1;
}

Без циклов, O(1).

Answer 3

Эта сумма равна (n*(n+1))^2/4.

Оцениваем, зная m, величину n как корень четвертной степени из 4m - с избытком. Дальше идем вниз, пока не получим совпадение или значение, явно меньшее m.

На C# не умею, на C++

long long FindNb(long long m)
{
    long long n = sqrt(sqrt(4*m))+1;
    for(;;--n)
    {
        long long sum = n*n*(n+1)*(n+1)/4;
        if (sum == m) return n;
        if (sum < m) return -1;
    }
}

Можно решать явно -

тут нужно просто аккуратненько с корнями работать... Просто функции sqrt() я бы не очень доверял. Как минимум, найдя - перепроверить...

Дополнительная оптимизация - если m не точный квадрат - заведомо возвращаем -1.

Answer 4

Если не использовать вариант (n * (n + 1))^2 / 4, то можно хотя бы не пересчитывать сумму для каждого i, а пользоваться суммой, полученной для i - 1:

public static long FindNb(long m)
{
    long sum = 0;
    for (var i = 1; sum < m; i++)
    {
        sum += (long)Math.Pow(i, 3.0);
        if (sum == m)
            return i;
    }
    return -1;
}

---

Если же вместо Math.Pow(i, 3.0) использовать просто (long)(i * i) * i или, если i гарантированно не будет превышать 1290 (что даёт сумму в 693 миллиарда), просто i * i * i (по предложению @rdorn), то работать будет ещё на порядок быстрее.

public static long FindNb(long m)
{
    long sum = 0;
    for (var i = 1; sum < m; i++)
    {
        sum += (long)(i * i) * i;
        if (sum == m)
            return i;
    }
    return -1;
}

---

Время работы для m = 1071225 при 100 тысячах итераций:

Первоначальный вариант:   5110мс  
Math.Pow + сумма:          227мс
i * i * i + сумма:          19мс
Код @VladD:                 10мс

Время работы для m равного 100 миллиардам при 100 тысячах итераций:

Первоначальный вариант: >60000мс  
Math.Pow + сумма:         3950мс
i * i * i + сумма:         255мс
Код @VladD:                  4мс