PROBLEM LINK:
Author: Swetanjal Murati Dutta
Tester: Radoslav Dimitrov
Editorialist: Akash Bhalotia
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
An encoder encodes the first 16 lowercase English letters using 4 bits. Each bit from the left signifies the half the letter lies in: if the first bit is 0, it means the letter lies among the first 8 letters of those 16 letters, else if it’s 1, it lies among the last 8. If the second bit is 0, it means the letter lies among the first 4 letters of those 8 letters, else if it’s 1, it lies among the last 4 letters of those 8 letters, and so on. Given an encoded string, decode it.
QUICK EXPLANATION:
show
Let’s take a four bit binary string. It corresponds to a decimal value between 0 and 15. Notice that a corresponds to 0, b to 1, c to 2, d to 3 \ldots p to 15. So, simply find the decimal value of the four-bit string and shift a by that many places to the right to get the decoded letter. Decoded all four-bit strings in the same way to get the final decoded string.
EXPLANATION
show
We are given an encoded binary string. Each four of its bits represent a lowercase English letter. Thus, there at most 2^4=16 lowercase letters representable using four bits. We need to decode the string into lowercase letters as per the method explained in the problem statement. So, the problem is pretty straightforward. We just need to understand how to decode each 4 of its bits into letters. After that we can go from left to right and create the decoded string by joining those letters.
Let’s try to understand how to decode a four-bit binary string into a letter. The first bit (from the left) tells us if it lies among the first 8 letters or the last 8 letters (of the 16 letters). If the bit is 0, then it lies among the first eight, else if its one, it lies among the last eight letters. Notice that in binary representation, if the leftmost bit of a four-bit binary number is set, it means that in the decimal representation, that number shall lie between 8 and 15 (both inclusive). If the leftmost bit is zero, it means that the number is less than 8, i.e., it lies between 0 and 7 (both inclusive). Thus, the first bit from the left in a four-bit binary number ‘contributes’ 8 to the decimal representation. It decides whether 8 will be added to the decimal representation or not.
So, if we were to convert the binary string to a decimal number, and its value was between 8 and 15, we would know that the letter lies among (i,j,k,l,m,n,o,p). If the decimal value was between 0 and 7, we would know that it lies among (a,b,c,d,e,f,g,h).
Similarly, the second bit (from the left) tells us if the letter lies among the first 4 or the last 4 of those 8 letters that we have narrowed it down to, from the value of the first bit. Again, if we think about the second bit in terms of binary and decimal values, we would observe that the second bit decides whether 4 would be added to the decimal value or not. The same goes for the third and fourth bits. The third bit contributes 2, and the fourth bit contributes 1 to the decimal value.
From these, we can infer that the decimal value of the 4 bit binary string is directly related to the lowercase letter it represents.
a corresponds to 0000 ( decimal value =0),
b to 0001 ( decimal value =1),
c to 0010 ( decimal value =2),
d to 0011 ( decimal value =3),
e to 0100 ( decimal value =4),
.
.
.
p to 1111 ( decimal value =15)
Thus, if we convert the four-bit binary string to decimal, we can find out which letter it represents. a + decimal value = letter it represents.
So, to solve the problem, start from the left, convert each four bits into decimal and find the corresponding letter it represents by shifting a by that many numbers. Finally, join all these letters to get the decoded string.
TIME COMPLEXITY:
show
The time complexity is: O(N)
Why?
We simply iterated over the binary string. We started from the left and converted each four bits to the corresponding decimal value. Converting takes constant time. Thus, the final time complexity is bounded by the length of the encoded string. Hence, it is O(N).
SOLUTIONS:
Tester
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n;
string s;
void read() {
cin >> n;
cin >> s;
}
void solve() {
for(int i = 0; i < n; i += 4) {
int x = 0;
for(int j = 0; j < 4; j++) {
x = (x << 1) | (s[i + j] - '0');
}
cout << (char)(x + 'a');
}
cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while (T-->0)
{
N=Integer.parseInt(br.readLine().trim());
char[] str=br.readLine().trim().toCharArray();
for(i=0;i<N;i+=4)
{
int pos=0,cur=1;
for(int j=i+3;j>=i;j--) //converting binary to decimal
{
if(str[j]=='1') pos+=cur;
cur*=2;
}
//finding the letter corresponding to the decimal
sb.append((char)('a'+pos));
}
sb.append("\n");
}
System.out.println(sb);
}
}
VIDEO EDITORIAL:
Feel free to share your approach if it differs. You can ask your doubts below.