Decryption

Easy
0/40
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in company
MAQ Software

Problem statement

You are given a string, 'MESSAGE'. The receiver of this ‘MESSAGE’ has a set of instructions on how to decrypt the message. In order to decrypt the message, we need to perform some rotation operations on the string.

These rotations can either be left rotations or right rotations. The set of instructions contains information about which type of rotation is to be performed and how many times. Your task is to determine the decrypted message.

Note:

Performing a 'left rotation' means deleting the first character of the string and appending it to the end of the string.

Performing a 'right rotation' means deleting the last character of the string and appending it to the beginning of the string.

For example, if we perform a left rotation on the string “coding”, it will become “odingc”. If we perform a right rotation on the string “ninja”, it will become “aninj”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single string, 'MESSAGE', 

The second line of each test case contains an integer, ‘N’, denoting the number of rotations we need to perform in order to decrypt the message. Then, ‘N’ lines follow. 

Each line contains two space-separated integers, ‘A’ and ‘B’. If ‘A’ is ‘-1’, you need to perform the left rotation on the string ‘MESSAGE’, ‘B’ times. If ‘A’ is ‘1’, you need to perform the right rotation, ‘B’ times.
Output Format: 
For each test case, return a single string, denoting the decrypted message after performing all the required operations.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |MESSAGE| <= 500
1 <= N <= 1000
N is always even

Time Limit: 1sec
Sample Input 1:
1
abcde 
4
-1 2
1 1
-1 2
-1 1
Sample Output 1:
eabcd
Explanation for sample input 1:
Initially, the given string is “abcde”. After performing the left rotation on it two times, we will get “cdeab”. After performing the right rotation on this string once, we will get “bcdea”. Next time, the string will become “deabc”. And finally, the string will become “eabcd”. Hence, we print the final result.
Sample Input 2:
1
babb 
3
-1 1
1 2
1 3
Sample Output 2:
babb
Explanation for sample input 2:
Initially, the given string is “babb”. After performing the left rotation on it once, we will get “abbb”. After performing the right rotation on this string two times, we will get “bbab”. And finally, the string will become “babb”. Hence, we print the final result.
Hint

If the size of the string is ‘LEN’, rotation of ‘LEN’ effectively means no rotation. 

Approaches (2)
Using Brute Force

Approach:

The approach is to observe the fact that if we perform a rotation operation, ’LEN * K’ times, where ‘LEN’ is the length of the string and ‘K’ is an arbitrary number, then we are effectively making no rotation in either direction. So, if we need to perform a rotation operation, ‘X’ number of times, we can perform it ‘X % LEN’ times, and we will still get the same result.

Another observation here is that if we want to perform the left rotation operation, ‘X’ times, then we can simply delete the first ‘X’ characters from the string and append them at the last of the string. Similarly, for the right rotation operation, we can delete the last ‘X’ characters and append them at the beginning of the string.

 

Steps:

  1. Run a loop from i=0 to i<'OPERATIONS'.size(), and do:
    1. Store the value of 'OPERATIONS'[i][1] in a variable, say rotation. This is the value of the number of rotations we have to perform in this operation.
    2. If 'OPERATIONS'[i][0]==-1, we need to perform left rotation, rotation times. So, call the function 'LEFT_ROTATE'(message, rotation). This function will rotate the string rotation times to the left.
    3. If 'OPERATIONS'[i][0]==1, we need to perform right rotation, rotation times. So, call the function rightRotate(message, rotation). This function will rotate the string rotation times to the right.
  2. Return the final message we get after performing all the 'OPERATIONS'.

void leftRotations(message, 'NUM') {

  1. Declare a variable, say 'LEN', to store the length of the string.
  2. Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
  3. Now, we need to delete the substring of size 'NUM', from the beginning of the string and append it at the end of the string. So, we make the value of message = message.substr('NUM', 'LEN' - 'NUM') + message.substr(0, 'NUM'). 

void rightRotations(message, 'NUM') {

  1. Declare a variable, say 'LEN', to store the length of the string.
  2. Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
  3. Now, we need to delete the substring of size 'NUM', from the end of the string and append it at the beginning of the string. So, we make the value of message = message.substr('LEN' - 'NUM', 'NUM') + message.substr(0, 'LEN' - 'NUM'). 
Time Complexity

O(N * M), where ‘N’ is the total number of rotation operations to be performed and ‘M’ is the length of the given string.

 

There are a total of ‘N’ rotation operations to be performed. In each operation, we need to make changes to the string which, in the worst case, can take O(M) time. So, the overall complexity will become O(N * M).

Space Complexity

O(1).

 

We are not using any extra auxiliary space.

Code Solution
(100% EXP penalty)
Decryption
Full screen
Console