Genomic Range Query is a problem from codility with the goal of finding the minimal nucleotide from a range of sequence DNA. Note that before attempting this problem, you should read the material on prefix sums.
In order to solve the problem I started by marking the position of each nucleotide in a 2D array. There are 4 nucleotides (A, C, G and T), so
a[i] will mark the position
i of nucleotide A as
1 if it appears in the string, otherwise
a[i] will have the value of
0. The same for
a[i] for nucleotide C, and so on.
Once we have the position of each nucleotide in the 2D array
a, we can proceed to compute the prefix sum of each of the nucleotides:
The final step is to return the value of the minimal impact factor of nucleotides contained in the given range. I did that by checking if the difference between the highest range prefix sum and the lowest returns a value above 0, if yes, then it means that a nucleotide of that impact factor must have occured, hence it’s our answer and we can break out of the loop.
The full solution can be found here.