Ninja's Encryption

Posted: 22 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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?
Approach 1

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’.
Try Problem