Project Euler 6. Feedback request. No brute force needed when math is done)

JavaScript
1

SPOILER ALERT. Working solution here. Don’t look in code if you wanna do it on your own.

Using some cool trick for dealing with nested loops. Such hint was kindly given to me in this thread
Wondering maybe I can optimize this code even more? No ideas for now.

function sumSquareDifference(n) {
  //assume have case >>> n = 3
  //sum of the squares >>> 1^2 + 2^2 + 3^2
  //square of the sums >>> 1^2 + 2^2 + 3^2 + 2(1 * 2) + 2 (1 * 3) + 2 * (2 * 3)

  //difference is obvious
  //need to find sum of products of pair combos of numbers from 1 to n
  //then multiply it by 2
  let result = 0;
  for (let i = 1; i <= n; i++) {
    //inner loop optimized >> to avoid duplicates
    //>>to avoid squares like (1 * 1)
    //to reduce loop steps (bigO better than O(n^2) here)
    for (let j = i + 1; j <= n; j++) { 
      result += i * j;
    }
  }
  return 2 * result;
}

sumSquareDifference(100);
2

I don’t know that this changes the big O of the algorithm.

There is a direct formula for the sum.

3

My logic was:
if we have something like
case 1

for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 3; i++) {
       console.log(i,j)
}
}

Above will be 3^2 lines in the console, and it’s classic nested loops O(n^2) situation

If we have some stuff like in solution
case 2

for (let i = 0; i < 3; i++) {
  for (let j = i; j < 3; i++) {
       console.log(i,j)
}
}

there will be 6 lines in the console. Its less complexity or not? Both cases are scalable, if we will increase size of the problem.

4

It is less iterations, but both iteration counts scale as O(n^2). Big O is all about the biggest term in the number of operations.

Your loops iterate n-1 + n-2 +… + 1 times, which is ~n^2 iterations.

1 Like
5

My research just led me to something called Efficient Polynomial-Time Nested Loop Fusion

But there is too much math terminology and my English is failing a little when it comes to maths.

6

When you answered, I was in the middle of some coding experiment, so I coded this:
note: not sure how can I call it? test function/ research function…?
Not sure if it is useful at all tho :upside_down_face:

//compare number of iterations
const countNumberOfIterations = (minSize, maxSize, step) => {
  
  
  //will print comparison for each problem size rom 1 to n
  for (let problemSize = minSize; problemSize <= maxSize; problemSize += step) {
    
    let countClassic = 0;
    let countJequalI = 0;
    
    for (let i = 0; i < problemSize; i++) {
      for (let j = 0; j < problemSize; j++) {
       countClassic++;
      }
    }
    for (let i = 0; i < problemSize; i++) {
      for (let j = i; j < problemSize; j++) {
       countJequalI++;
      }    
    }
    
    console.log('For the problemsize ' ,problemSize);
    console.log('Classic loops do ', countClassic, ' iterations.')
    console.log('J equal I situation gives ', countJequalI, ' iterations.');
    console.log('Relative complexity(classic to jequali)', countClassic/countJequalI)
    console.log('-----------------')
  }
}

countNumberOfIterations(10, 100, 10);
/*
For the problemsize  10
Classic loops do  100  iterations.
J equal I situation gives  55  iterations.
Relative complexity(classic to jequali) 1.8181818181818181
-----------------
For the problemsize  20
Classic loops do  400  iterations.
J equal I situation gives  210  iterations.
Relative complexity(classic to jequali) 1.9047619047619047
-----------------
For the problemsize  30
Classic loops do  900  iterations.
J equal I situation gives  465  iterations.
Relative complexity(classic to jequali) 1.935483870967742
-----------------
For the problemsize  40
Classic loops do  1600  iterations.
J equal I situation gives  820  iterations.
Relative complexity(classic to jequali) 1.951219512195122
-----------------
For the problemsize  50
Classic loops do  2500  iterations.
J equal I situation gives  1275  iterations.
Relative complexity(classic to jequali) 1.9607843137254901
-----------------
For the problemsize  60
Classic loops do  3600  iterations.
J equal I situation gives  1830  iterations.
Relative complexity(classic to jequali) 1.9672131147540983
-----------------
For the problemsize  70
Classic loops do  4900  iterations.
J equal I situation gives  2485  iterations.
Relative complexity(classic to jequali) 1.971830985915493
-----------------
For the problemsize  80
Classic loops do  6400  iterations.
J equal I situation gives  3240  iterations.
Relative complexity(classic to jequali) 1.9753086419753085
-----------------
For the problemsize  90
Classic loops do  8100  iterations.
J equal I situation gives  4095  iterations.
Relative complexity(classic to jequali) 1.978021978021978
-----------------
For the problemsize  100
Classic loops do  10000  iterations.
J equal I situation gives  5050  iterations.
Relative complexity(classic to jequali) 1.9801980198019802
-----------------
*/
7

A few things here

  1. Big O complexity is a very crude metric. Big O talks about how the amount of work scales as n gets massive. In this case, a double nested loop does kn^2 operations while your modified double nested loop has k/2n^2 operations. You saw that factor of 2 in your experiments. That’s the same complexity class in each approach. Big O does not care about the factor of two.

  2. That said, the algorithm you wrote requires you to cut out these extra iterations for correctness. You should always do exactly as many loop iterations as you need. No more or less.

  3. It is important to remember that Big O is only one tool in writing good code.

  4. There exists a O(1) solution to this problem.

  5. Polynomial time loop fusion is something a compiler would do. I don’t think most JS engines would do it. In any case, O(n^2) is polynomial complexity already.

1 Like
8

So there is just some simple formula for that somewhere? And inside function will be one line of code basically?
I’ve heard that some euler problems can be solved with pencil/paper tools.
EDIT. I guess I found that on fCC page with solution.

By the way, on the page with solution to this problem some strange stuff is going on.
In explanation of the problem there are blank lines where formulas should be.

9

Followed up question(to make sure):
O(n^2) and O(n^3) >>> this is one class of complexity? Can I say that it’s all one class of complexity, which is O(n^c)?
And different class of complexity would be, for example O(c^n)?

10

Yeah, there exists a formula.

O(n^2) and O(n^3) are different complexity classes.

11

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.