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 hereExpected 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] = 0 sum[1] = numbers[0] sum[2] = numbers[0] + numbers[1] sum[3] = numbers[0] + numbers[1] + numbers[2] …
This precomputed data structure will allow you to answer the queries efficiently. For instance sum(1,3) = sum[4] – sum[1]. 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])
}
}
func answerQueries() {
for queryPair in queries {
print(query(a:queryPair.0, b:queryPair.1))
}
}
func partialSums() {
initializeSums()
answerQueries()
}
partialSums()[collapse]
