 Partial Sums

You are given one array of numbers and another one with pairs (a,b) representing questions of the type: What is the sum of the numbers between position a and b in the array? Efficiently compute the answer to the given questions and print them.

Example

Input:

let numbers = [3, 6, 4, 15, 30]
let queries = [(1,3),(0,4)]

// your code here

Expected value/output:

25
58

[collapse]
Hint

You can either compute the result for each query, which would be inefficient. Or you can use an array to store the following sums:

sum = 0 sum = numbers sum = numbers + numbers sum = numbers + numbers + numbers …

This precomputed data structure will allow you to answer the queries efficiently. For instance sum(1,3) = sum – sum. This operation has O(1) complexity.

[collapse]
Solution

let numbers = [3, 6, 4, 15, 30]
let queries = [(1,3),(0,4)]
var sums: [Int] = []

func query(a:Int, b:Int) -> Int {
return sums[b+1] - sums[a]
}

func initializeSums() {
sums.append(0)
for i in 0..<numbers.count {
sums.append(sums.last! + numbers[i])
}
}

for queryPair in queries {
print(query(a:queryPair.0, b:queryPair.1))
}
}

func partialSums() {
initializeSums()     (No Ratings Yet) Loading...