Encoded String Codechef January Challenge 2021

 Encoded String Problem Code: DECODEIT

An encoder encodes the first 16$16$ lowercase English letters using 4$4$ bits each. The first bit (from the left) of the code is 0$0$ if the letter lies among the first 8$8$ letters, else it is 1$1$, signifying that it lies among the last 8$8$ letters. The second bit of the code is 0$0$ if the letter lies among the first 4$4$ letters of those 8$8$ letters found in the previous step, else it's 1$1$, signifying that it lies among the last 4$4$ letters of those 8$8$ letters. Similarly, the third and the fourth bit each signify the half in which the letter lies.

For example, the letter j$j$ would be encoded as :

• Among (a,b,c,d,e,f,g,h$(a,b,c,d,e,f,g,h$ |$|$ i,j,k,l,m,n,o,p)$i,j,k,l,m,n,o,p)$, j$j$ appears in the second half. So the first bit of its encoding is 1$1$.
• Now, among (i,j,k,l$(i,j,k,l$ |$|$ m,n,o,p)$m,n,o,p)$, j$j$ appears in the first half. So the second bit of its encoding is 0$0$.
• Now, among (i,j$(i,j$ |$|$ k,l)$k,l)$, j$j$ appears in the first half. So the third bit of its encoding is 0$0$.
• Now, among (i$(i$ |$|$ j)$j)$, j$j$ appears in the second half. So the fourth and last bit of its encoding is 1$1$.

So j$j$'s encoding is 1001$1001$,

Given a binary encoded string S$S$, of length at most 105${10}^5$, decode the string. That is, the first 4 bits are the encoding of the first letter of the secret message, the next 4 bits encode the second letter, and so on. It is guaranteed that the string's length is a multiple of 4.

Input:

• The first line of the input contains an integer T$T$, denoting the number of test cases.
• The first line of each test case contains an integer N$N$, the length of the encoded string.
• The second line of each test case contains the encoded string S$S$.

Output:

For each test case, print the decoded string, in a separate line.

Constraints

• 1≤T≤10$1\le T\le 10$
• 4≤N≤105$4\le N\le {10}^5$
• The length of the encoded string is a multiple of 4$4$.
• 0≤Si≤1$0\le S_i\le 1$

Subtasks

• 100$100$ points : Original constraints.

Sample Input:

3
4
0000
8
00001111
4
1001

Sample Output:

a
ap
j

Explanation:

• Sample Case 1$1$ :

The first bit is 0$0$, so the letter lies among the first 8$8$ letters, i.e., among a,b,c,d,e,f,g,h$a,b,c,d,e,f,g,h$. The second bit is 0$0$, so it lies among the first four of these, i.e., among a,b,c,d$a,b,c,d$.

The third bit is 0$0$, so it again lies in the first half, i.e., it's either a$a$ or b$b$. Finally, the fourth bit is also 0$0$, so we know that the letter is a$a$.

• Sample Case 2$2$ :

Each four bits correspond to a character. Just like in sample case 1$1$, 0000$0000$ is equivalent to a$a$. Similarly, 1111$1111$ is equivalent to p$p$. So, the decoded string is ap$ap$.

• Sample Case 3$3$ :

The first bit is 1$1$, so the letter lies among the last 8$8$ letters, i.e., among i,j,k,l,m,n,o,p$i,j,k,l,m,n,o,p$. The second bit is 0$0$, so it lies among the first four of these, i.e., among i,j,k,l$i,j,k,l$.

The third bit is 0$0$, so it again lies in the first half, i.e., it's either i$i$ or j$j$. Finally, the fourth bit is 1$1$, so we know that the letter is j$j$.

Encoded String Solution in C++ :

#include<bits/stdc++.h>

#define ll long long 

#include<string>

using namespace std;

void solve()

{

    ll int n;

    cin>>n;

    string temp,ans="";

    char s[n];

    for(ll int i=0;i<n;i++)

    {

        cin>>s[i];

    }

    for(ll int i=0;i<n;i+=4)

    {

        temp="";

        temp+=s[i];

        temp+=s[i+1];

        temp+=s[i+2];

        temp+=s[i+3];

        if(temp=="0000") ans+="a";

        else if(temp=="0001") ans+="b";

        else if(temp=="0010") ans+="c";

        else if(temp=="0011") ans+="d";

        else if(temp=="0100") ans+="e";

        else if(temp=="0101") ans+="f";

        else if(temp=="0110") ans+="g";

        else if(temp=="0111") ans+="h";

        else if(temp=="1000") ans+="i";

        else if(temp=="1001") ans+="j";

        else if(temp=="1010") ans+="k";

        else if(temp=="1011") ans+="l";

        else if(temp=="1100") ans+="m";

        else if(temp=="1101") ans+="n";

        else if(temp=="1110") ans+="o";

        else if(temp=="1111") ans+="p";

    }

    cout<<ans<<"\n";

}

int main()

{

    ll t;   cin>>t;     while(t--)

    {

        solve();

    }

}

Encoded String For Solution in C : Checkout Here (Actual Logic)