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] = 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]
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)