# Help with sum of element pairs in Pairwise*

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

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

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

1 Like

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

1 Like

Hello! No, I haven´t tried it yet. That sometimes confuses me 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
``````
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 indeces=[];
let sumOfIndeces=[];

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

//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]))
}
}
sumOfIndeces.push(indeces[i]+indeces[i+1])
}
}

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

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);
``````

Why not keep a list of ‘used’ indices?

1 Like

I will try that. Thanks for the tip.

1 Like

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

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);
``````

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
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

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

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

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

``````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);``````

I am thankful to you for your answers @caryaharper @JeremyLT @Sylvant @ilenia @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);``````

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

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

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.

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