Author: SQU_Test
DIFFICULTY:
Easy
PREREQUISITES:
Basic observations.
PROBLEM:
Nasser is mad about coding, that is why he writes encoded messages. He calls the median letter in a word the letter, which is in the middle of the word. If the word’s length is even, the median letter is the left of the two middle letters. In the following examples, the median letter is highlighted: contest, info. If the word consists of single letter, then according to above definition this letter is the median letter.
Nasser encodes each word in the following way: he writes down the median letter of the word, then deletes it and repeats the process until there are no letters left. For example, he encodes the word volga as logva.
You are given an encoding s of some word; your task is to decode it.
EXPLANATION:
To find the answer we can iterate through the given string from the left to the right and add each letter in the answer string — one letter to the beginning, next letter to the end, next letter to beginning and so on. If n is even then the first letter must be added to the beginning and the second letter to the end. In the other case, the first letter — to the end, second — to the beginning. We need to make it until we do add all letters from the given string.
TIME COMPLEXITY:
Time complexity of the solution is O(n).
SOLUTIONS:
Setter’s Solution
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n;
string word, newWord;
cin>>n;
cin>>word;
newWord = "";
for (int j= 0; j<n; j++)
if (((n%2 == 1) && (j%2 == 0)) || ((n%2 == 0) && (j%2 == 1)) )
newWord = newWord + word[j];
else
newWord = word[j] + newWord;
cout<<newWord<<endl;
return 0;
}