Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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)
like image 935
mcavoybn Avatar asked Sep 18 '25 22:09

mcavoybn


2 Answers

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

Now iterate over a once -> O(n)

like image 180
Jochen Bedersdorfer Avatar answered Sep 20 '25 12:09

Jochen Bedersdorfer


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

like image 25
abdullah ajibade Avatar answered Sep 20 '25 12:09

abdullah ajibade