CODEWITHSUNDEEP
javascriptnode.jsalgorithmtime-complexityspace-complexity
Dawid Wraga
Dawid Wraga

Reputation: 3

Methods of decreasing algorythm complexity

I am trying to programme a function that takes a non-negative integer, and returns a list of non-negative integer pairs whose values - when squared - sum to the given integer.

examples:

  5  -->  [ [1, 2] ]
 25  -->  [ [0, 5], [3, 4] ]
325  -->  [ [1, 18], [6, 17], [10, 15] ]

My solution works in an IDE but when I submit it to codewars I receive exit code error 139: FATAL ERROR: invalid table size Allocation failed - JavaScript heap out of memory. The codewars documentation indicates that this is due to an inefficient algorythm.

Initially my solution contained a nested loop which was causing long run time but I have since refactored my code to remove this. Despite this reduced complexity I still get the same error.

Any suggestions how I can further decrease the complexity?

const allSquaredPairs = (n) => {
//get array of all numbers between 0 and sqrt of n
let possibleNums = Array(n)
.fill()
.map((_, i) => {
  if ((i + 1) ** 2 <= n) return i + 1; //only numbers lesser than sqrt of n
})
.filter(n => n!=undefined)
possibleNums = [0, ...possibleNums];

const matchingPairs = [];
while (possibleNums.length){

    const num1 = possibleNums[0];
    const num2 = possibleNums[possibleNums.length-1];
    const sum = num1 ** 2 + num2 ** 2

    if (sum === n) matchingPairs.push([num1, num2]);
  
    if (sum > n ) possibleNums.pop()
    else possibleNums.shift()


  }
return matchingPairs;
};
console.log(allSquaredPairs(25));

Upvotes: 0

Views: 77

Answers (1)

alexanderbird
alexanderbird

Reputation: 4198

Your solution allocates an array of length n, and then iterates over it. That means that the memory requirement for your solution increases linearly as n increases.

You could implement this without allocating that array so that the memory requirement is constant no matter how large the value of n.

const examples = [
  { input:   5, output: [ [1, 2] ] },
  { input:  25, output: [ [0, 5], [3, 4] ] },
  { input: 325, output: [ [1, 18], [6, 17], [10, 15] ] },
  { input: Number.MAX_SAFE_INTEGER, output: [] }
];

function allSquaredPairs(n) {
  const matchingPairs = [];
  const smallestIntegerLargerThanSquareRootOfN = Math.ceil(Math.sqrt(n));
  let lowerBound = 0;
  let upperBound = smallestIntegerLargerThanSquareRootOfN;
  while (lowerBound < upperBound) {
    const sum = lowerBound ** 2 + upperBound ** 2;

    if (sum === n) {
      matchingPairs.push([lowerBound, upperBound]);
      lowerBound += 1;
    } else if (sum < n) lowerBound += 1;
    else if (sum > n) upperBound -= 1;
    else console.log("ERROR!")
  }
  return matchingPairs;
}

examples.forEach(({ input, output}) => console.log({ n: input, expected: JSON.stringify(output), "  actual": JSON.stringify(allSquaredPairs(input)) }));

As a point of interest, I tried this with let whatever = new Array(n) at the start of the function, and for the max safe integer test case it threw RangeError: invalid array length. That's a different error than you were seeing, but it does illustrate how allocating an array of length n can complicate things.

Upvotes: 2

Related Questions