Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Trying to optimize my code to either remove nested loop or make it more efficient

  • A friend of mine takes a sequence of numbers from 1 to n (where n > 0)

  • Within that sequence, he chooses two numbers, a and b

  • He says that the product of a and b should be equal to the sum of all numbers in the sequence, excluding a and b

  • Given a number n, could you tell me the numbers he excluded from the sequence?

Have found the solution to this Kata from Code Wars but it times out (After 12 seconds) in the editor when I run it; any ideas as too how I should further optimize the nested for loop and or remove it?

function removeNb(n) {
  var nArray = [];
  var sum = 0;
  var answersArray = [];
  for (let i = 1; i <= n; i++) {
    nArray.push(n - (n - i));
    sum += i;
  }
  var length = nArray.length;
  for (let i = Math.round(n / 2); i < length; i++) {
    for (let y = Math.round(n / 2); y < length; y++) {
      if (i != y) {
        if (i * y === sum - i - y) {
          answersArray.push([i, y]);
          break;
        }
      }
    }
  }
  return answersArray;
}

console.log(removeNb(102));
.as-console-wrapper { max-height: 100% !important; top: 0; }
like image 347
Ashton Hauser Avatar asked May 04 '19 22:05

Ashton Hauser


People also ask

How can we reduce the complexity of nested loops?

Putting all together. Continuing on the challenge to reduce the iterations on our algorithm, we have to perform the following steps: build the "index" with the information to be accessed later. iterate over the loop and fetch the additional information from the previously created "index"

Are nested loops inefficient?

Nested loops may be an inefficient solution, and there may be a better solution.

Can nested loops cause performance issues?

Nested Loops can greatly reduce the innovative potential of the code because it negatively impacts performance.


2 Answers

I think there is no reason for calculating the sum after you fill the array, you can do that while filling it.

function removeNb(n) {
    let nArray = [];
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        nArray.push(i);
        sum += i;
    }
}

And since there could be only two numbers a and b as the inputs for the formula a * b = sum - a - b, there could be only one possible value for each of them. So, there's no need to continue the loop when you find them.

if(i*y === sum - i - y) {
    answersArray.push([i,y]);
    break;
}

I recommend looking at the problem in another way.

You are trying to find two numbers a and b using this formula a * b = sum - a - b.

Why not reduce the formula like this:

a * b + a = sum - b

a ( b + 1 ) = sum - b

a = (sum - b) / ( b + 1 )

Then you only need one for loop that produces the value of b, check if (sum - b) is divisible by ( b + 1 ) and if the division produces a number that is less than n.

for(let i = 1; i <= n; i++) {
    let eq1 = sum - i;
    let eq2 = i + 1;
    if (eq1 % eq2 === 0) {
        let a = eq1 / eq2;
        if (a < n && a != i) {
            return [[a, b], [b, a]];
        }
    }
}
like image 100
Hassan Saleh Avatar answered Sep 19 '22 06:09

Hassan Saleh


You can solve this in linear time with two pointers method (page 77 in the book).

In order to gain intuition towards a solution, let's start thinking about this part of your code:

for(let i = Math.round(n/2); i < length; i++) {
    for(let y = Math.round(n/2); y < length; y++) {
        ...

You already figured out this is the part of your code that is slow. You are trying every combination of i and y, but what if you didn't have to try every single combination?

Let's take a small example to illustrate why you don't have to try every combination.

Suppose n == 10 so we have 1 2 3 4 5 6 7 8 9 10 where sum = 55.

Suppose the first combination we tried was 1*10.

Does it make sense to try 1*9 next? Of course not, since we know that 1*10 < 55-10-1 we know we have to increase our product, not decrease it.

So let's try 2*10. Well, 20 < 55-10-2 so we still have to increase.

3*10==30 < 55-3-10==42

4*10==40 < 55-4-10==41

But then 5*10==50 > 55-5-10==40. Now we know we have to decrease our product. We could either decrease 5 or we could decrease 10, but we already know that there is no solution if we decrease 5 (since we tried that in the previous step). So the only choice is to decrease 10.

5*9==45 > 55-5-9==41. Same thing again: we have to decrease 9.

5*8==40 < 55-5-8==42. And now we have to increase again...


You can think about the above example as having 2 pointers which are initialized to the beginning and end of the sequence. At every step we either

  • move the left pointer towards right
  • or move the right pointer towards left

In the beginning the difference between pointers is n-1. At every step the difference between pointers decreases by one. We can stop when the pointers cross each other (and say that no solution can be obtained if one was not found so far). So clearly we can not do more than n computations before arriving at a solution. This is what it means to say that the solution is linear with respect to n; no matter how large n grows, we never do more than n computations. Contrast this to your original solution, where we actually end up doing n^2 computations as n grows large.

like image 21
Atte Juvonen Avatar answered Sep 18 '22 06:09

Atte Juvonen