prefix sum

A collection of 4 post

Passing Cars

Problem A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of…

Min Avg Two Slice

Problem A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of AP + AP + 1 + … + AQ divided by the length of the slice…

Genomic Range Query

Problem A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and…

Count Div

Problem Write a function: that, given three integers A, B and K, returns the number of integers within the range A..B that are divisible by K, i.e.: { i : A ≤ i ≤ B, i mod K = 0 } For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by…