Tasks Details
medium
Find the minimal nucleotide from a range of sequence DNA.
Task Score
62%
Correctness
100%
Performance
0%
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 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
For example, consider string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6The answers to these M = 3 queries are as follows:
- The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
- The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
- The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:
class Solution { public int[] solution(string S, int[] P, int[] Q); }
that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
Result array should be returned as an array of integers.
For example, given the string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6the function should return the values [2, 4, 1], as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [1..50,000];
- each element of arrays P and Q is an integer within the range [0..N - 1];
- P[K] ≤ Q[K], where 0 ≤ K < M;
- string S consists only of upper-case English letters A, C, G, T.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C#
Time spent on task 54 minutes
Notes
not defined yet
Code: 07:55:46 UTC,
cs,
verify,
result: Passed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
}
return result;
}
}
Analysis
Code: 07:58:11 UTC,
cs,
verify,
result: Passed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
Analysis
expand all
User tests
1.
0.054 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.054 s
OK
function result: [2]
function result: [2]
1.
0.054 s
OK
function result: [1]
function result: [1]
Code: 08:02:22 UTC,
cs,
verify,
result: Passed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.041 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.054 s
OK
function result: [2]
function result: [2]
1.
0.053 s
OK
function result: [1]
function result: [1]
1.
0.055 s
OK
function result: [2, 3, 2, 3, 3]
function result: [2, 3, 2, 3, 3]
Code: 08:18:12 UTC,
cs,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
case default:
result = 0;
break;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(47,17): error CS1525: Unexpected symbol `default:'
Code: 08:18:25 UTC,
cs,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
default:
result = 0;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.056 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.053 s
OK
function result: [2]
function result: [2]
1.
0.054 s
OK
function result: [1]
function result: [1]
1.
0.054 s
OK
function result: [2, 3, 2, 3, 3]
function result: [2, 3, 2, 3, 3]
Code: 08:22:45 UTC,
cs,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
default:
result = 0;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.034 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.053 s
OK
function result: [2]
function result: [2]
1.
0.041 s
OK
function result: [1]
function result: [1]
1.
0.043 s
OK
function result: [2, 3, 2, 3, 3]
function result: [2, 3, 2, 3, 3]
Code: 08:24:37 UTC,
cs,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
default:
result = 0;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
User test case 5:
['CAT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.054 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.052 s
OK
function result: [2]
function result: [2]
1.
0.055 s
OK
function result: [1]
function result: [1]
1.
0.052 s
OK
function result: [2, 3, 2, 3, 3]
function result: [2, 3, 2, 3, 3]
1.
0.054 s
OK
function result: [1, 1, 2, 1, 1]
function result: [1, 1, 2, 1, 1]
Code: 08:29:13 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
for(int i = 0; i < P.Length; i++)
{
int p = CheckImpact(S.Substring(P[i],1));
int q = CheckImpact(S.Substring(Q[i],1));
if(p < q)
{
result[i] = p;
}
else
{
result[i] = q;
}
}
return result;
}
int CheckImpact(string s)
{
int result = 0;
switch(s)
{
case "A":
result = 1;
break;
case "C":
result = 2;
break;
case "G":
result = 3;
break;
case "T":
result = 4;
break;
default:
result = 0;
break;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
User test case 5:
['CAT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.035 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.033 s
OK
function result: [2]
function result: [2]
1.
0.035 s
OK
function result: [1]
function result: [1]
1.
0.034 s
OK
function result: [2, 3, 2, 3, 3]
function result: [2, 3, 2, 3, 3]
1.
0.034 s
OK
function result: [1, 1, 2, 1, 1]
function result: [1, 1, 2, 1, 1]
Code: 08:45:13 UTC,
cs,
verify,
result: Failed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
int[] impact = new int[dna.Length];
for(int i = 0; i < dna.Length; i++)
{
switch(dna[i])
{
case "A":
impact[i] = 1;
break;
case "C":
impact[i] = 2;
break;
case "G":
impact[i] = 3;
break;
case "T":
impact[i] = 4;
break;
default:
impact[i] = 0;
break;
}
}
for(int i = 0; i < P.Length; i++)
{
int value = 0;
for(int K = P[i]; K <= Q[i]; K++)
{
if(value < impact[K]) value = impact[K];
}
result[i] = value;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 4 error(s), 0 warnings Solution.cs(17,18): error CS0029: Cannot implicitly convert type `string' to `char' Solution.cs(20,18): error CS0029: Cannot implicitly convert type `string' to `char' Solution.cs(23,18): error CS0029: Cannot implicitly convert type `string' to `char' Solution.cs(26,18): error CS0029: Cannot implicitly convert type `string' to `char'
Code: 08:48:22 UTC,
cs,
verify,
result: Failed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
int[] impact = new int[dna.Length];
for(int i = 0; i < dna.Length; i++)
{
switch(dna[i])
{
case 'A':
impact[i] = 1;
break;
case 'C':
impact[i] = 2;
break;
case 'G':
impact[i] = 3;
break;
case 'T':
impact[i] = 4;
break;
default:
impact[i] = 0;
break;
}
}
for(int i = 0; i < P.Length; i++)
{
int value = 0;
for(int K = P[i]; K <= Q[i]; K++)
{
if(value < impact[K]) value = impact[K];
}
result[i] = value;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
User test case 5:
['CAT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got [3, 4, 4] expected [2, 4, 1]
expand all
User tests
1.
0.055 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.055 s
OK
function result: [2]
function result: [2]
1.
0.056 s
OK
function result: [0]
function result: [0]
1.
0.055 s
OK
function result: [3, 4, 0, 4, 0]
function result: [3, 4, 0, 4, 0]
1.
0.056 s
OK
function result: [2, 4, 0, 4, 0]
function result: [2, 4, 0, 4, 0]
Code: 08:49:02 UTC,
cs,
verify,
result: Passed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
int[] impact = new int[dna.Length];
for(int i = 0; i < dna.Length; i++)
{
switch(dna[i])
{
case 'A':
impact[i] = 1;
break;
case 'C':
impact[i] = 2;
break;
case 'G':
impact[i] = 3;
break;
case 'T':
impact[i] = 4;
break;
default:
impact[i] = 0;
break;
}
}
for(int i = 0; i < P.Length; i++)
{
int value = 10;
for(int K = P[i]; K <= Q[i]; K++)
{
if(impact[K] < value) value = impact[K];
}
result[i] = value;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
User test case 5:
['CAT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.056 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.057 s
OK
function result: [2]
function result: [2]
1.
0.057 s
OK
function result: [10]
function result: [10]
1.
0.056 s
OK
function result: [2, 3, 10, 3, 10]
function result: [2, 3, 10, 3, 10]
1.
0.056 s
OK
function result: [1, 1, 10, 1, 10]
function result: [1, 1, 10, 1, 10]
Code: 08:49:12 UTC,
cs,
verify,
result: Passed
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
int[] impact = new int[dna.Length];
for(int i = 0; i < dna.Length; i++)
{
switch(dna[i])
{
case 'A':
impact[i] = 1;
break;
case 'C':
impact[i] = 2;
break;
case 'G':
impact[i] = 3;
break;
case 'T':
impact[i] = 4;
break;
default:
impact[i] = 0;
break;
}
}
for(int i = 0; i < P.Length; i++)
{
int value = 10;
for(int K = P[i]; K <= Q[i]; K++)
{
if(impact[K] < value) value = impact[K];
}
result[i] = value;
}
return result;
}
}
User test case 1:
['C', [0, 0, 0], [0, 0, 0]]
User test case 2:
['C', [0], [0]]
User test case 3:
['CAGCCTACAGCCTACAGCCTACAGCCTACAGCCTACAGCCTA', [20], [10]]
User test case 4:
['CGT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
User test case 5:
['CAT', [0, 1, 2, 1, 2], [1, 2, 0, 2, 1]]
Analysis
expand all
User tests
1.
0.056 s
OK
function result: [2, 2, 2]
function result: [2, 2, 2]
1.
0.056 s
OK
function result: [2]
function result: [2]
1.
0.056 s
OK
function result: [10]
function result: [10]
1.
0.033 s
OK
function result: [2, 3, 10, 3, 10]
function result: [2, 3, 10, 3, 10]
1.
0.033 s
OK
function result: [1, 1, 10, 1, 10]
function result: [1, 1, 10, 1, 10]
Code: 08:49:15 UTC,
cs,
final,
score:
62
using System;
class Solution {
public int[] solution(string S, int[] P, int[] Q) {
if(S.Length < 1 || 100000 < S.Length || P.Length == 0 || 50000 < P.Length || Q.Length == 0 || 50000 < Q.Length || P.Length != Q.Length) throw new InvalidOperationException();
int[] result = new int[P.Length];
char[] dna = S.ToCharArray();
int[] impact = new int[dna.Length];
for(int i = 0; i < dna.Length; i++)
{
switch(dna[i])
{
case 'A':
impact[i] = 1;
break;
case 'C':
impact[i] = 2;
break;
case 'G':
impact[i] = 3;
break;
case 'T':
impact[i] = 4;
break;
default:
impact[i] = 0;
break;
}
}
for(int i = 0; i < P.Length; i++)
{
int value = 10;
for(int K = P[i]; K <= Q[i]; K++)
{
if(impact[K] < value) value = impact[K];
}
result[i] = value;
}
return result;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N * M)
expand all
Correctness tests
1.
0.053 s
OK
2.
0.055 s
OK
3.
0.053 s
OK
4.
0.055 s
OK
1.
0.055 s
OK
2.
0.053 s
OK
3.
0.055 s
OK
4.
0.055 s
OK
1.
0.052 s
OK
2.
0.055 s
OK
3.
0.052 s
OK
1.
0.053 s
OK
1.
0.054 s
OK
expand all
Performance tests
almost_all_same_letters
GGGGGG..??..GGGGGG..??..GGGGGG
GGGGGG..??..GGGGGG..??..GGGGGG
✘
TIMEOUT ERROR
running time: 4.74 sec., time limit: 0.40 sec.
running time: 4.74 sec., time limit: 0.40 sec.
1.
4.742 s
TIMEOUT ERROR,
running time: 4.74 sec., time limit: 0.40 sec.
2.
0.058 s
OK
large_random
large random string, length
large random string, length
✘
TIMEOUT ERROR
running time: 4.26 sec., time limit: 0.39 sec.
running time: 4.26 sec., time limit: 0.39 sec.
1.
4.263 s
TIMEOUT ERROR,
running time: 4.26 sec., time limit: 0.39 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.40 sec.