DNASTORAGE Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Daanish Mahajan
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

To be Calculated

PREREQUISITES:

None

PROBLEM:

For encoding an even-length binary string into a sequence of A, T, C, and G, we iterate from left to right and replace the characters as follows:

  • 00 is replaced with A
  • 01 is replaced with T
  • 10 is replaced with C
  • 11 is replaced with G

Given a binary string S of length N (N is even), find the encoded sequence.

EXPLANATION:

This is a simple implementation problem. We can run a for loop with an increment of 2 and for each two characters we can compare and output result as follows:
Suppose we are at the i_{th} pointer, then

if \; s[i] = 0 \; and \; s[i+1] = 0, \; output \; A \\ if \; s[i] = 0 \; and \; s[i+1] = 1, \; output \; T \\ if \; s[i] = 1 \; and \; s[i+1] = 0, \; output \; C \\ if \; s[i] = 1 \; and \; s[i+1] = 1, \; output \; G

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution