Help with sum of element pairs in Pairwise*

JavaScript
#1

Tell us what’s happening:
How can I get the sum of Indices in element pairs? I am speaking about the array sumOfIndices.
Your code so far


function pairwise(arr, arg) {
let copyOfArr=arr;
let sumOfAddedNum=[];
let indeces=[];
let sumOfIndeces=[];
    for(let i=0;i<copyOfArr.length;i++){
        for(let j=0;j<arr.length;j++){
          sumOfAddedNum.push(copyOfArr[i]+arr[j])
          indeces.push(copyOfArr.indexOf(copyOfArr[i]))
          indeces.push(arr.indexOf(arr[j]))
        }
    }
   for(let i=0;i<sumOfAddedNum.length;i+=1){
          sumOfIndeces.push(indeces[i]+indeces[i+1])
    }
    console.log(sumOfAddedNum,indeces,sumOfIndeces)
}

pairwise([1,4], 5);

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.114 Safari/537.36.

Challenge: Pairwise

Link to the challenge:

1 Like
#2

edit: nvm i saw the challenge, ill have to give it a look :wink:
PS: have you tried checking the hints section?

1 Like
#3

Hello! No, I haven´t tried it yet. That sometimes confuses me :frowning:

#4

Can you try to explain, in words what each line in your code is doing? I think you have some good parts but they aren’t working together in a cohesive ‘big picture’ to get the answer.

1 Like
#5 

function pairwise(arr, arg) {

  //copyOfArr just points to the same array as arr 
  let copyOfArr=arr;
  console.log(copyOfArr === arr) //true
  //you can double loop through the same array without out
  //the need for a copy

  let sumOfAddedNum=[];
  let indeces=[];
  let sumOfIndeces=[];
    
    for(let i=0;i<copyOfArr.length;i++){
        for(let j=0;j<arr.length;j++){

          sumOfAddedNum.push(copyOfArr[i]+arr[j])

          //You already have access to the index, 
          //the index is i or j,
          //also indexOf only gets the first intances of
          //an element so this would not work for repeated elements
          indeces.push(copyOfArr.indexOf(copyOfArr[i]))
          indeces.push(arr.indexOf(arr[j]))
        }
    }
   for(let i=0;i<sumOfAddedNum.length;i+=1){
          sumOfIndeces.push(indeces[i]+indeces[i+1])
    }
    console.log(sumOfAddedNum,indeces,sumOfIndeces)
}

pairwise([1,4], 5);

This is commenting out somethings that are probably not working the way you think they are. If you would, write out what you want to do in whatever your primary language is and then try to do that in code. If you write out you want to do as a comment I can help you with the logic of it.

1 Like
#6

This works fine with three tests but I am failing to set how to get the Indeces of duplicate numbers

function pairwise(arr, arg) {
  let sumOfIndex=0
  for(let i=0;i<arr.length;i++){
    for(let j=0;j<arr.length;j++){
          if(arr[i]+arr[j]==arg && arr.indexOf(arr[i])!=arr.indexOf(arr[j])){
                sumOfIndex+=arr.indexOf(arr[i])+arr.indexOf(arr[j])
          }
    }

  }
  //console.log(sumOfIndex/2)
           return sumOfIndex/2
}

pairwise([1, 3, 2, 4], 4);
#7

Why not keep a list of ‘used’ indices?

1 Like
#8

I will try that. Thanks for the tip.

1 Like
#9

if you find an i-j match, can you still use the i?

also, consider, does j always needs to start from 0? don’t you check couples again like that?

2 Likes
#10

If I sum in pain in pair, I can get every test pass but this pairwise([0, 0, 0, 0, 1, 1], 1) should return 10.

function pairwise(arr, arg) {
  let indecesOfElementPairs=[]
  let sumOfElementPairs=[]
  let indecesList=[];
  let sumOfIndeces=0; 
  
  for(let i=0;i<arr.length;i++){
      indecesList.push(i)
   }
   for(let i=1;i<arr.length;i++){
       for(let j=0;j<arr.length;j++){
            if(arr[i]+arr[j]===arg){
                 indecesOfElementPairs.push(i,j)       
            }   
       }
   }
  
  let uniq = [...new Set(indecesOfElementPairs)]; 
  console.log(indecesOfElementPairs,uniq)
  
}

pairwise([1, 1, 1], 2);
#11

I deleted things you were not using

function pairwise(arr, arg) {
  let indecesOfElementPairs=[]
  
  
   for(let i=0;i<arr.length;i++){

      //you should not be looking at elements
     //you have already passed
       for(let j= 0;j<arr.length;j++){

         //if this block executes both indexes can no longer be used
         //and you should break the loop for the same reason.
         //you should invalidate any indexes that have been valid
            if(arr[i]+arr[j]===arg){
                 indecesOfElementPairs.push(i,j)
                 //invalidate indexes here
                 //stop loop here       
            }   
       }
   }
  
  //You do not need uniq if you get the above comments to work
  let uniq = [...new Set(indecesOfElementPairs)]; 
  console.log(indecesOfElementPairs,uniq)
  
}

pairwise([1, 1, 1], 2);

I got the code to pass with a bit of refactoring, if you have any further questions feel free to ask

this is how you break
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/break

1 Like
#12

ive used includes:

function pairwise(arr, arg) {

let sum=0

let val

let used=

for(let i=0;i<arr.length-1;i++){

for(let j=i+1;j<arr.length;j++){

  if(arr[i]+arr[j]===arg){

    if(!used.includes(i)&&!used.includes(j)){

    val=i+j

    sum+=val

    used.push(i,j)

    }

  }

}

}

return sum

}

pairwise([1,1,1], 2);

the problem with that is includes is linear:

You could delete the index entirely i.e. splice… yet that would not be efficient.
I think you could set the element at the index to some null value…

What would be the most efficient way to do it?

1 Like
#13

I am not an expert with time complexity and its notation, but I believe my personal solution would have been O(n*log(n)). I used the following logic:

//obj = create an object to save what I've used {};
//sum = 0, to be the return value

/*
for elements of a given list {
 check obj in constant time
 if (obj[element has been used]) skip element

 for elements after given element in list {
  if (element[i] + element[j] === v) {
   obj[j] = value has been used
   sum = sum + (i + j)
   break loop as i has been used
  }
 }
}
 return sum
/*

In this example the amount of elements you loop through decreases each iteration so it is not o(n ^ 2).

In your current example it would be essentially a double loop as you are not providing a second argument to includes which means it will loop through the entirety of the array and while having two includes in your use does not increase time complexity it will cause it to take longer as it simply has more work to do.

1 Like
#14

yea i see your example is making a cache… memoization…

I could have used find instead… I just wanted to solve the problem fast… but thats moot. yeah I see your example above is probably a better way to go about it…

1 Like
#15

I am thankful to you for your answers

function pairwise(arr, arg) {
  let newArr=[]
  let arrOfIndexes=[]
  let counter=0    
    for(let i=0;i<arr.length;i++){
           for(let j=0;j<arr.length;j++){
               if(i!=j && arg==arr[i]+arr[j] &&  !newArr.includes(i) && !newArr.includes(j)){
                       newArr.push(i,j)
                                    
               } 
           }
      }
      for(let i=0;i<newArr.length;i++){
           counter+=newArr[i]
      }
        return counter
     
}

pairwise([0, 0, 0, 0, 1, 1], 1);
#16

I am thankful to you for your answers @caryaharper @JeremyLT @Sylvant @ieahleen @kravmaguy

function pairwise(arr, arg) {
  let newArr=[]
  let arrOfIndexes=[]
  let counter=0    
    for(let i=0;i<arr.length;i++){
           for(let j=0;j<arr.length;j++){
               if(i!=j && arg==arr[i]+arr[j] &&  !newArr.includes(i) && !newArr.includes(j)){
                       newArr.push(i,j)
                                    
               } 
           }
      }
      for(let i=0;i<newArr.length;i++){
           counter+=newArr[i]
      }
        return counter
     
}

pairwise([0, 0, 0, 0, 1, 1], 1);
#17

why start i and j both at zero, and then only afterwards you add it all? efficient way is how @caryaharper mentioned. with a cache…
you understand why what you wrote is not so good?

1 Like
#18

we should not use includes… look again at the pseudocode of what caryaharper wrote. if you use a cache it will be instant lookup:

the above screenshot i think could be referring to when multiple things hash to the same key, (bucket size is small) then you would have to iterate through the linked list at that spot(key) to find it and it would take time… But in javascript object I think its instant you will never have more than one at the same key.

1 Like
#19

Yes, I understand the reason why is not good. It is not efficient. I do not know how to do it according to her instructions.

#20

The best you can do is an O(n^2) algo. In the worst case:
The first item needs to be compared against n-1 items
The second item needs to be compared against n-2 items
…
The second to last item needs to be compared against 1 item

So we have ((n-1) * n) / 2 === (n^2 - n)/2 element comparisons

The real savings is in how you check if an index has been used.

There are two basic multi-element data structures in JavaScript, the array and the object.

Option 1) Use an array - so long as your array is allocated up-front, it is O(1) to index into an array or modify the array

Option 2) Use an object - this can also be O(1) to index, but the constant is bigger for hash lookups than array lookups for relatively small arrays (In JS, maybe < 1 million elements? I’m not sure)

The question is how to store the data in the object or array. This affects how well you can look up the data.

For an array, you can either keep an array of all visited indices or you can keep a boolean array that keeps the visited status of each index. One is much faster than the other.

For an object, I’d just add the index as a property if it has been visited and leave it unset if it has not.

1 Like