Skip to content

Instantly share code, notes, and snippets.

@arielm
Last active September 11, 2016 14:59
Show Gist options
  • Save arielm/9ca320825bc3602544fa05f5af4e0a1b to your computer and use it in GitHub Desktop.
Save arielm/9ca320825bc3602544fa05f5af4e0a1b to your computer and use it in GitHub Desktop.
Solution (100%) to GenomicRangeQuery problem on Codility (https://codility.com/programmers/task/genomic_range_query/)
/*
* I WAS ONLY CAPABLE OF FINDING AN O(N*M) SOLUTION
*
* THE O(N+M) SOLUTION PRESENTED HERE IS BASED ON:
* http://csharplabtests.blogspot.co.il/2015/06/codility-lesson-3-genomicrangequery.html
*/
class Solution
{
public int[] solution(String S, int[] P, int[] Q)
{
int N = S.length();
int[][] count = new int[N + 1][4];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 4; j++)
{
count[i + 1][j] = count[i][j];
}
switch (S.charAt(i))
{
case 'A':
count[i + 1][0]++;
break;
case 'C':
count[i + 1][1]++;
break;
case 'G':
count[i + 1][2]++;
break;
case 'T':
count[i + 1][3]++;
break;
}
}
int M = P.length;
int[] results = new int[M];
for (int i = 0; i < M; i++)
{
int i0 = P[i];
int i1 = Q[i];
for (int j = 0; j < 4; j++)
{
if (count[i1 + 1][j] - count[i0 + 0][j] > 0)
{
results[i] = j + 1;
break;
}
}
}
return results;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment