# LintCode: Take the element and query the sum

Take the element and query the sum

Similar Problems:

Description
Now you have n numbers, save them in the arr array. You need to select any two numbers and multiply them , ask the sum of all these possibilities is. Return the sum.The return value is modulo 1000000007.

1 <= n <= 100000

Example

```Give arr=[1,2,3,4,5] , return 85.

[1,2], 1*2=2
[1,3], 1*3=3
[1,4], 1*4=4
[1,5], 1*5=5
[2,3], 2*3=6
[2,4], 2*4=8
[2,5], 2*5=10
[3,4], 3*4=12
[3,5], 3*5=15
[4,5], 4*5=20
2+3+4+5+6+8+10+12+15+20=85
```
```Give arr=[2,4,4,6,8] , return 220.

[2,4], 2*4=8
[2,4], 2*4=8
[2,6], 2*6=12
[2,8], 2*8=16
[4,4], 4*4=16
[4,6], 4*6=24
[4,8], 4*8=32
[4,6], 4*6=24
[4,8], 4*8=32
[6,8],6*8=48
8+8+12+16+16+24+32+24+32+48=220
```

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/take-the-element-and-query-the-sum
// Basic Ideas: Two pass
// Complexity: Time O(n), Space O(1)
/**
* @param arr: the arr
* @return: the sum
*/
func takeTheElementAndQueryTheSum (arr []int) int {
mod := 1000000007
sum := 0
for _, v:= range arr {
sum = (sum + v) % mod
}

res, sum2 := 0, 0
for _, v:= range arr {
sum2 = (sum2 + v) % mod
res = (res + v*(sum-sum2) % mod) % mod
}

return res
}
```

Share It, If You Like It.