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

Question

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

Answer 1

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

Answer 2

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.