Algorithm that checks if the sum of any two items in a sorted array equals a number producing erroneous results

Question

Algorithm that checks if the sum of any two items in a sorted array equals a number producing erroneous results

Navigation

#1 by (0 votes)
#2 by (0 votes)

-2

This pairSum algorithm must find whether the sum of any two items in a sorted arr array is equal to a given target number:

    function pairSum(arr, target){

    for (var i=0; i<arr.length;){

        for (var j = arr.length-1; j>i;){

            if (i=j) {return false} else {

                if (arr[i] + arr[j] === target){ //we have our case

                    return true;

                } else if (arr[i]+arr[j] < target) { //we don't have our case, but we know the last item (right index = j) needs to stay on the calculation, so we only change i

                    i++;

                } else {

                    j--; //we still don't have our case, but we know the last item (right index = j) is not part of the solution, so we skip it to the left, and we keep the left item (index = i)

                }
           }; 
        };

    };
    return false;

};

//invocation // current result // desired result
console.log( pairSum( [3,4,6,8,9,11], 14) ); //false // true because 11+3=14
console.log( pairSum( [3,4,6,8,9,11], 8)  ); //false // false
console.log( pairSum( [3,4,4,8,9,11], 8)  ); //false // true because 4+4=8
console.log( pairSum( [3,4,6,8,9,11], 16) ); //false // false
console.log( pairSum( [3,4,6,8,9,11], 20) ); //false // true because 11+9=20

javascript algoritmo

asked by anonymous 18.07.2015 / 23:35

2 answers

Receive input value and pass in URL How to do this insertion dynamically?

score 0 · Answer 1

function pairSum(target, number){
  for(var i in target){
    for(var j in target){
      if(i == j) continue;
      if(target[i] + target[j] == number) return true;
    }
  }
  return false;
}

console.log( pairSum( [3,4,6,8,9,11], 14) ); //true because 11+3=14
console.log( pairSum( [3,4,6,8,9,11], 8)  ); //false
console.log( pairSum( [3,4,4,8,9,11], 8)  ); //true because 4+4=8
console.log( pairSum( [3,4,6,8,9,11], 16) ); //false
console.log( pairSum( [3,4,6,8,9,11], 20) ); //true because 11+9=20

score 0 · Answer 2

Two errors were complicating the solution of the algorithm:

if (i=j) {return false} else {

should be:

if (i===j) {return false} else {

This causes the algorithm to correctly evaluate positive cases, but becomes an infinite loop in negative cases. This can be easily fixed by transforming:

} else if (arr[i]+arr[j] < target) {

in:

} else if (arr[i]+arr[j] <= target) {

Final code, therefore, stays:

    function pairSum(arr, target){

    for (var i=0; i<arr.length;){

        for (var j = arr.length-1; j>=i;){

            if (i===j) {return false} else {

                if (arr[i] + arr[j] === target){ //we have our case

                    return true;

                } else if (arr[i]+arr[j] <= target) { //we don't have our case, but we know the last item (right index = j) needs to stay on the calculation, so we only change i

                    i++;

                } else {

                    j--; //we still don't have our case, but we know the last item (right index = j) is not part of the solution, so we skip it to the left, and we keep the left item (index = i)

                }
           }; 
        };

    };
    return false;

};

console.log( pairSum( [3,4,6,8,9,11], 14) ); //true 
console.log( pairSum( [3,4,6,8,9,11], 8)  ); //false 
console.log( pairSum( [3,4,4,8,9,11], 8)  ); //true 
console.log( pairSum( [3,4,6,8,9,11], 16) ); //false
console.log( pairSum( [3,4,6,8,9,11], 20) ); //true