Last Updated: 22 Apr, 2021

Ninja's Encryption

Easy

Asked in companies

Solve now

Problem statement

Ninja has created his own encryption technique to encrypt a number. He makes use of the logic behind factorial. In a factorial, we multiply the number by its previous number and so on but if we want to encrypt a number we don’t multiply in every step like in the case of factorial but multiply, divide, add and subtract and repeat in the same order.

So your task is to find the encrypted form of a number using the ninja encryption technique and you were being provided with the number.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the given number.

Output Format:

For each test case, print a single line containing the encrypted form of the number.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000

Time Limit: 1 sec

Follow Up:

Can you do this in constant time and space?

Solve now

Approaches

01 Approach

The idea here is very simple as you can see that we are simply applying operations like multiply and divide and alternatively we are adding and subtracting the result. So we just have to find the result of every three numbers in every iteration and we can simply do the required operations alternatively.

Algorithm:

Firstly we declare three variables ‘ans’ for storing the final answer, ‘result’ for storing the evaluation of multiplication, division, and a boolean type flag which help us in alternatively subtracting and adding.
Now iterate until our ‘N’ is greater than ‘0’.
In every iteration we check
- If ‘N >= 3 we store result = N * (N - 1) / (N - 2) and update ‘N = N - 3’
- Else if N == 2 we store result = N * N - 1 and update ‘N = N - 2’
- Else if N == 1 we store result = N and update ‘N = N - 1’
Now we check ‘flag’ == true then we add that ‘result’ to ‘ans’ i.e. do ans += result and make flag = false.
Else if flag == false then we subtract result from ‘ans’ i.e.do ans -= result
Now after division, we know we have to add so we check
- If N >= 1 we add ‘N’ in the result i.e do result += N and update ‘N = N - 1’
After this, we simply return the ‘ans’.

Solve now

02 Approach

The idea here is to divide the problem in the form of ‘4’ and we can then simply find the result for ‘0’, ‘1’, ‘2’, ‘3’ elements as after every ‘4’ times the same operators are repeated.

Algorithm:

Firstly we check If ‘N <= 2’ we return ‘N’ as we know ( 2 * ( 2 - 1) ) = 2.
Now we check If ‘N <= 4’ we return ‘N + 3’ as we can say that if ‘N == 3’ or ‘N == 4’ we get ‘6’ and ‘7’ respectively.
Now we check:
- If ‘(N - 4) % 4 == 0' we return ‘N + 1’ as we can say that if ‘N == 8 or 12’ we get ‘9’ and ‘13’ respectively.
- Else if ‘(N - 4) % 4 <=2' we return ‘N + 2’ as we can say that if ‘N == 6’ we get ‘8’.
Else we simply return ‘N -1’.

Solve now