My algorithm is a little off and super inefficient
I am trying to implement an algorithm called Sum of Pairs on the Codewars website . I wrote an algorithm, but it doesn't pass all tests and takes a long time to process. Please can you suggest me how to solve this problem correctly and efficiently. Thank!
Instructions follow
sum_pairs([11, 3, 7, 5], 10)
# ^--^ 3 + 7 = 10
== [3, 7]
sum_pairs([4, 3, 2, 3, 4], 6)
# ^-----^ 4 + 2 = 6, indices: 0, 2 *
# ^-----^ 3 + 3 = 6, indices: 1, 3
# ^-----^ 2 + 4 = 6, indices: 2, 4
# * entire pair is earlier, and therefore is the correct answer
== [4, 2]
sum_pairs([0, 0, -2, 3], 2)
# there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)
sum_pairs([10, 5, 2, 3, 7, 5], 10)
# ^-----------^ 5 + 5 = 10, indices: 1, 5
# ^--^ 3 + 7 = 10, indices: 3, 4 *
# * entire pair is earlier, and therefore is the correct answer
== [3, 7]
My code:
var sum_pairs=function(ints, s){
var total = 0;
var list = [];
for (var i=0; i < ints.length; i++) {
for (var j=1; j < ints.length; j++) {
total = ints[i]+ints[j];
if (total === s) {
list.push(ints[i], ints[j]);
return list;
}
//console.log(total);
}
}
}
sum_pairs([1,2,3,4,1,0], 2);
And this test fails:
✘ First Match From Left REDUX!: [10,5,2,3,7,5] should return [3, 7] for sum = 10
+1
source to share
4 answers
You cannot use O (N ^ 2) algorithms if you are expecting arrays of 10M elements. How about the code below:
var sum_pairs=function(ints, s, und){
var h = {}
for(var i=ints.length - 1; i >= 0; --i){
h[ints[i]] = i
}
for(var i=0; i < ints.length; ++i){
var ci = ints[i]
var e = h[s - ci]
if(e < i){
return [s - ci, ci]
}
}
return und
}
+2
source to share
Try this code, it works in all cases. Edit: I've only done the parsing once and it uses a hash. This is a better solution than before. Runs for ~ 5000ms. Try to go through this thread to learn more about this logic: Link
var sum_pairs=function(arr, num){
var len=arr.length,i,j,hash = {},first_index,second_index;
for(i=0;i<len;i++){
var looking_for = num - arr[i]
if(looking_for in hash){
first_index = hash[looking_for];
second_index = i;
return [arr[first_index], arr[second_index]];
}
hash[arr[i]] = i;
}
}
+3
source to share
Now with some acceleration mechanisms like
- single cycle,
- hash table for visited values
- variable
a
for elementarray[i]
It takes 153ms for a long list .
var sum_pairs = function (array, s) {
var a, i,
hash = Object.create(null);
for (i = 0; i < array.length; i++) {
a = array[i];
if (hash[s - a]) {
return [s - a, a];
}
if (!hash[a]) {
hash[a] = true;
}
}
};
console.log(sum_pairs([11, 3, 7, 5], 10)); // [3, 7]
console.log(sum_pairs([4, 3, 2, 3, 4], 6)); // [4, 2]
console.log(sum_pairs([0, 0, -2, 3], 2)); // undefined
console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10)); // [3, 7]
console.log(sum_pairs([1, 2, 3, 4, 1, 0], 2)); // [1, 1]
console.log(sum_pairs([1, -2, 3, 0, -6, 1], -6)); // [0, -6]
console.log(sum_pairs([0, 2, 0], 0)); // [0, 0]
console.log(sum_pairs([5, 9, 13, -3], 10)); // [13, -3]
.as-console-wrapper { max-height: 100% !important; top: 0; }
+1
source to share
Try it,
var sum_pairs=function(ints, s){
var total = 0;
var list = [];
//skip the last num
for (var i=0; i < ints.length-1; i++) {
//skip nums which is greater than s
if(ints[i]>=s){
continue;
}
//start from i+1
for (var j=i+1; j < ints.length; j++) {
total = ints[i]+ints[j];
if (total === s) {
list.push(ints[i], ints[j]);
return list;
}
//console.log(total);
}
}
}
0
source to share