Task

I solve the problem on Codewars : find for the following formula n^3 + (n-1)^3 + ... + 1^3 = m number n . The number m is known and passed to the FindNb function. If n does not exist for the passed m , then the answer is -1. For example:

FindNb(1071225) --> 45

FindNb(91716553919377) --> -1

My decision

This is what I did:

 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; }

Question

My solution works , but the service requires optimizing the code (it takes too long to complete). How to do it?

  • the complexity of my algorithm was quadratic (N ^ 2). I do not know how to reduce it.
  • I also thought the cast could ...(long)Math.Pow... slows down the code, but the search for optimization in this part also did not work.

    4 answers 4

    And if you try this option, without nested loops:

     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; }

    The thing is: the account goes back, from one:

    with n = 1 we have the formula 1 ^ 3

    for n = 2 we have the formula 2 ^ 3 + 1 ^ 3

    for n = 3 we have the formula 3 ^ 3 + 2 ^ 3 + 1 ^ 3

    and so on. We accumulate the result and at each iteration we look, if we didn’t miss our “standard” in the size of m. If they coincide with the standard, we deduce the loop counter, if not ("we jumped too much") - we deduce -1.

    I have a Stopwatch showing on the 100 repetitions of the code the acceleration by an order of magnitude (initial version, optimized):

     16386 1309
    • four
      one more order to win by replacing (long)Math.Pow(i, 3.0) with i * i * i . For small integer powers this works much faster than Math.Pow - rdorn
    • one
      @rdorn is a pretty good idea. I added this option to my answer along with work speed measurements. - Regent

    The implementation of the idea from the @Harry answer with the formula S = [n(n+1)/2]^2 and the square root:

     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; }

    Without cycles, O (1).

      This sum is equal to (n * (n + 1)) ^ 2/4.

      Evaluating, knowing m, the value of n as the fourth-degree root of 4m is in excess. Then we go down until we get a match or a value that is clearly less than m.

      On C # I do not know how, on 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; } }

      You can decide explicitly -

      enter image description here

      here you just need to work neatly with the roots ... I would not really trust the sqrt() functions. At least by finding - double-checking ...

      Additional optimization - if m not an exact square - we obviously return -1.

      • 2
        And why evaluate, pick up? the equation is perfectly solved analytically ... - Akina
      • @Akina Well, yes, but we are interested in integer solutions - so you still need to check. Always do not trust the roots of integers, etc. math :) - Harry
      • we are interested in integer solutions - so you still have to check. Well, check by reverse multiplication ... however, given that the square root will be short, you only need to check the last digit (the penultimate one just has to be exact). Checking (which do not use) will still be easier and cheaper than iterative selection. - Akina
      • @Akina Selection will be no more than 1-2 samples. - Harry
      • 2
        Damn, we work in positive integers ... then no selection is needed at all, for ROUND_DOWN(SQRT(x * (x + 1)) = x . - Akina

      If you do not use the option (n * (n + 1))^2 / 4 , then you can at least not recalculate the amount for each i , but use the amount obtained for 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; }

      If instead of Math.Pow(i, 3.0) you simply use (long)(i * i) * i or, if i guaranteed not to exceed 1290 (which gives an amount of 693 billion), simply i * i * i (according to the proposal @rdorn), then it will work an order of magnitude faster.

       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; }

      Operating time for m = 1071225 with 100 thousand iterations:

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

      Operating time for m equal to 100 billion with 100 thousand iterations:

       Первоначальный вариант: >60000мс Math.Pow + сумма: 3950мс i * i * i + сумма: 255мс Код @VladD: 4мс
      • i can immediately issue the long type, and there will be no restriction, but I remember that MS had some problems with the for and long cycle on x86 , so in this case I would use while - rdorn
      • @rdorn I have a variant with long i = 1 works twice as long (long)(i * i) * i (I tested it yesterday too), so I refused it. - Regent