Last Updated: 18 Apr, 2021
Decryption
Easy
Asked in company
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”.
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
Approaches
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:
- Run a loop from i=0 to i<'OPERATIONS'.size(), and do:
- 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.
- 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.
- 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.
- Return the final message we get after performing all the 'OPERATIONS'.
void leftRotations(message, 'NUM') {
- Declare a variable, say 'LEN', to store the length of the string.
- Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
- 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') {
- Declare a variable, say 'LEN', to store the length of the string.
- Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
- 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').
Approach:
We can observe that making some rotation operations in one direction and making the same number of rotation operations in the opposite direction effectively means making no rotations at all. So, we can calculate the effective number of rotations we need to perform and the direction in which we need to perform these rotations.
We can achieve this by keeping a variable, say 'ACTUAL_ROTATIONS', with its value initialized to zero. Whenever we are asked to perform a left rotation, ‘X’ number of times, we can simply subtract ‘X’ from 'ACTUAL_ROTATIONS'. If we are asked to perform a right rotation, ‘X’ number of times, then we can simply add ‘X’ to 'ACTUAL_ROTATIONS'.
Now, if the value of 'ACTUAL_ROTATIONS' is negative, this means that we need to perform left rotations, ‘X’ number of times, where ‘X’ is the value of 'ACTUAL_ROTATIONS'. And if ‘X’ is positive, we perform the right rotations, ‘X’ times.
Steps:
- Initialize a variable, say 'ACTUAL_ROTATIONS' = 0. This will store the value of actual shifts to be performed. If its value is negative, then we need to perform the left rotations, and if the value is positive, then we need to perform the right rotations.
- Run a loop from ‘i’ = 0 to ‘i’ < ‘OPERATIONS’.size(), and do:
- 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.
- If ‘OPERATIONS[i][0]’ == -1, we need to perform left rotation, rotation times. So, subtract rotation from 'ACTUAL_ROTATIONS'.
- If ‘OPERATIONS[i][0] == -1’, we need to perform right rotation, rotation times. So, add rotation to 'ACTUAL_ROTATIONS'.
- If the value of 'ACTUAL_ROTATIONS' is negative, then this means that we have to effectively rotate the string in the left direction. So, call the function, ‘LEFT_ROTATE’(MESSAGE, abs('ACTUAL_ROTATIONS')).
- If the value of 'ACTUAL_ROTATIONS' is positive, then this means that we have to effectively rotate the string in the right direction. So, call the function, ‘RIGHT_ROTATE’(message, 'ACTUAL_ROTATIONS').
- Return the final message we get after performing all the operations.
void LEFT_ROTATE(message, 'NUM') {
- Declare a variable, say 'LEN', to store the length of the string.
- Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
- 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') {
- Declare a variable, say 'LEN', to store the length of the string.
- Take modulo of 'NUM' by 'LEN'. Formally, make 'NUM' %= 'LEN'.
- 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').