The task is the following: the user is given a sequence of numbers from 1 to n, we check whether the product of two numbers from the sequence can be equal to the sum of all numbers of the sequence, not counting these 2 numbers. For example: a series from 1 to n, where n = 26. The product of the numbers 15 and 21 is equal to the sum of all the numbers except 21 and 15. Here is the code:

using System.Collections.Generic; public class RemovedNumbers { public static int Sum(long n) { int sum=0; for(int i =1;i<=n;i++) { sum+=i; } return sum; } public static List<int[]> removNb(long n) { int sum=Sum(n); List <int[]> list = new List<int []>(); int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i*j == sum-(i+j)) { list.Add(new int [] {i,j}); list.Add(new int [] {j,i}); return list; } } } return list; } }

The code runs in 0.015 seconds, you need to optimize to 0.008, what do you advise?

  • I advise you not to use the compile to baytkod when it comes to squeezing milliseconds - Vladimir Martyanov
  • @ Vladimir Martiyanov: the JIT compiler compiles the bytecode into native compiler quite well. But in general, it is better to solve not by squeezing cycles, but by editing the algorithm. - VladD

3 answers 3

In a double loop, you run all pairs of numbers twice (since you may have i > j and i < j ).
Therefore, you can easily double the speed.

Instead:

 int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { ... } }

Write down:

 for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { ... } }

Plus, as @pavel correctly pointed out, it is more reasonable to calculate the sum of the natural series not by a cycle, but by the formula:

 int sum = n * (n + 1) / 2;
  • The division by bit shift is more reasonable to replace. - justyx
  • @justyx First, with optimization turned on, the compiler should do this. Secondly, this operation in the code is a one-time. I do not think that there are conditions under which you can notice differences in runtime, even without optimization turned on. - Dmitry D.

Well, at least so I can advise: (for N = 1) does not work.

  const int N = 26; int r; int sum = N*(N+1)/2; for (int i=N/2;i<=N;i++) if ( (sum - i) % (i+1) == 0) if ( (r = (sum - i) / (i+1) ) <= N) // {i,r} ответ

You can think a little further in this direction.

And where does the big numbers? On the contrary, all numbers are less than 1000.

By the way, if the restrictions on N are small, it makes sense to predict everything in advance

    Alas, not familiar with C #. But - at least it is enough to check numbers greater than n/2 and up to n+1 , as dividers n(n+1)/2-1 - then the first number is one less than, well, and the second is clear ... We get at least O(n) instead of O(n^2) .

    In C ++, it looks like this:

     bool check(int n, int&k, int&m) { int s = n*(n+1)/2 + 1; for(m = n/2 + 1; m <= n + 1; ++m) if (s%m == 0) { k = (n*(n+1)+2)/2/m-1; if (k == m-1) continue; m--; return true; } return false; }

    As I understand it, the numbers should not be the same? type, 1 + 2 + 3 + 4 + 5 = 15, 15-6 = 9, 9 = 3 * 3 - not suitable?