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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.