Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

respectable

Find the minimal nucleotide from a range of sequence DNA.

Programming language:
Spoken language:

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:

The answers to these M = 3 queries are as follows:

- The part of the DNA between positions 2 and 4 contains nucleotides
GandC(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
Awhose impact factor is 1, so the answer is 1.

Assume that the following declarations are given:

struct Results { int * A; int M; };

Write a function:

struct Results solution(char *S, int P[], int Q[], int M);

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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:

The answers to these M = 3 queries are as follows:

- The part of the DNA between positions 2 and 4 contains nucleotides
GandC(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
Awhose impact factor is 1, so the answer is 1.

Write a function:

vector<int> solution(string &S, vector<int> &P, vector<int> &Q);

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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:

The answers to these M = 3 queries are as follows:

- The part of the DNA between positions 2 and 4 contains nucleotides
GandC(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
Awhose 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 zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Assume that the following declarations are given:

Results = record A : array of longint; M : longint; end;

Write a function:

function solution(S: PChar; P: array of longint; Q: array of longint; M: longint): Results;

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

def solution(S, P, Q)

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

class Solution { public int[] solution(string S, int[] P, int[] Q); }

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

function solution($S, $P, $Q);

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

function solution(S, P, Q);

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

sub solution { my ($S, $P, $Q)=@_; my @P=@$P; my @Q=@$Q; ... }

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

def solution(s, p, q)

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

Private Function solution(S As String, P As Integer(), Q As Integer()) As Integer()

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

function solution(S, P, Q)

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

NSMutableArray * solution(NSString *S, NSMutableArray *P, NSMutableArray *Q);

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

object Solution { def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] }

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

func Solution(S string, P []int, Q []int) []int

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

public func solution(inout S : String, inout _ P : [Int], inout _ Q : [Int]) -> [Int]

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

`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?

`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:

The answers to these M = 3 queries are as follows:

GandC(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.T, whose impact factor is 4, so the answer is 4.Awhose impact factor is 1, so the answer is 1.

Write a function:

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int]

The sequence should be returned as:

- a Results structure (in C), or
- a vector of integers (in C++), or
- a Results record (in Pascal), or
- an array of integers (in any other programming language).

For example, given the string S = `CAGCCTA` and arrays P, Q such that:

the function should return the values [2, 4, 1], as explained above.

Assume that:

- 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, 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.

Complexity:

- expected worst-case time complexity is O(N+M);

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN