CODEWITHSUNDEEP
javascriptcomplexity-theory
mcavoybn
mcavoybn

Reputation: 51

How to convert this O(n^2) algorithm to O(n)?

https://www.codewars.com/kata/is-my-friend-cheating/train/javascript

My goal is to devise a function that finds number pairs (a, b) which satisfy the equation a * b == sum(1, 2, 3 ..., n-2, n-1, n) - a - b.

The following code finds all the pairs, but is too slow and times out. I have seen in the comments for this challenge that the algorithm needs to have O(n) complexity to pass. How is this done? 

function removeNb (n) {
  if(n===1) return null;

  let sum = (n * (n+1))/2;

  let retArr = [];
  let a = n;
  while( a !== 0){
    let b = n;
    while( b !== 0){
       if(b != a && a*b == ((sum - b) - a) ){
         retArr.push([a,b]);
       }
       b--;
    }
    a--;
  }
  retArr.sort( (a,b) => a[0] - b[0]);
  return retArr;
}

Thanks to all for the assistance! Here is my final solution:

function removeNb (n) {
  let retArr = [];
  let a = 1;
  let b = 0;
  let sumN = (n * (n+1))/2; 

  while( a <= n){
    b = parseInt((sumN - a) / (a + 1));
    if( b < n && a*b == ((sumN - b) - a) ) 
      retArr.push([a,b]);
    a++;
  }
  return retArr;
}

I think my main issue was an (embarrassing) error with my algebra when I attempted to solve for b. Here are the proper steps for anyone wondering: 

a*b = sum(1 to n) - a - b
ab + b = sumN - a
b(a + 1) = sumN - a
b = (sumN - a) / (a + 1)

Upvotes: 4

Views: 6170

Answers (4)

abdullah ajibade
abdullah ajibade

Reputation: 52

let n = 100;
let sumOfNum = n => {
  return (n * (n + 1)) / 2;
};
let sum = sumOfNum(n);
let response = [];
for (let i = 1; i <= 26; i++) {
  let s = (sum - i) / (i + 1);
  if (s % 1 == 0 && s * i == sum - s - i && s <= n) {
    response.push([s, i]);
  }
}

// this is O(N) time complexity

Upvotes: 1

Franz
Franz

Reputation: 534

As explained in other answers, it is possible to make a O(n) algorithm solving for b. Moreover, given the symmetry of solution -- if (a,b) is a solution, also (b,a) is -- it is also possible to save some iterations adding a couple of solutions at a time. To know how many iterations are required, let us note that b > a if and only if a < -1+sqrt(1+sum). To prove it: 

(sum-a)/(a+1) > a ; sum-a > a^2+a ; sum > a^2+2a ; a^2+2a-sum < 0 ; a_1 < a < a_2

where a_1 and a_2 comes from 2-degree equation solution:

a_1 = -1-sqrt(1+sum) ; a_2 = -1+sqrt(1+sum)

Since a_1 < 0 and a > 0, finally we proved that b > a if and only if a < a_2.

Therefore we can avoid iterations after -1+sqrt(1+sum).

A working example:

function removeNb (n) {
  if(n===1) return null;
  let sum = (n * (n+1))/2;
  let retArr = [];
  for(let a=1;a<Math.round(Math.sqrt(1+sum));++a) {
      if((sum-a)%(a+1)===0) {
          let b=(sum-a)/(a+1);
          if(a!==b && b<=n) retArr.push([a,b],[b,a]);
      } 
  }
  retArr.sort( (a,b) => a[0] - b[0]);
  return retArr;
}

However, with this implementation we still need the final sort. To avoid it, we can note that b=(sum-a)/(a+1) is a decreasing function of a (derive it to prove). Therefore we can build retArr concatenating two arrays, one adding elements to the end (push), one adding elements at the beginning (unshift). A working example follows:

function removeNb (n) {
  if(n===1) return null;
  let sum = (n * (n+1))/2;
  let retArr = [];
  let retArr2 = [];
  for(let a=1;a<Math.round(Math.sqrt(1+sum));++a) {
      if((sum-a)%(a+1)===0) {
          let b=(sum-a)/(a+1);
          if(a!==b && b<=n) {
              retArr.push([a,b]);
              retArr2.unshift([b,a]); // b>a and b decreases with a
          }
      } 
  }
  retArr=retArr.concat(retArr2); // the final array is ordered in the 1st component
  return retArr;
}

As a non-native speaker, I would say that the phrase from the reference "all (a, b) which are the possible removed numbers in the sequence 1 to n" implies a!=b, so I added this constraint.

Upvotes: 0

Derek 朕會功夫
Derek 朕會功夫

Reputation: 94319

Here's an implementation:

function removeNb(n){
    var sum = (1 + n) * n / 2;
    var candidates = [];

    // O(n)
    for(var y = n; y >= 1; y--){
        x = (-y + sum) / (y + 1);

        /*
         * Since there are infinite real solutions,
         * we only record the integer solutions that
         * are 1 <= x <= n.
         */
        if(x % 1 == 0 && 1 <= x && x <= n)
            // Assuming .push is O(1)
            candidates.push([x, y]);
    }

    // Output is guaranteed to be sorted because
    // y is iterated from large to small.
    return candidates;
}

console.log(removeNb(26));
console.log(removeNb(100));

https://jsfiddle.net/DerekL/anx2ox49/

From your question, it also states that

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

However it does not mention that a and b are unique numbers, so a check is not included in the code.

Upvotes: 0

Jochen Bedersdorfer
Jochen Bedersdorfer

Reputation: 4122

You can solve for b and get: b = (sum - a)/(a + 1) (given a != -1)

Now iterate over a once -> O(n)

Upvotes: 2

Related Questions