Last Updated: 28 Aug, 2021

Monster Game

Moderate

Asked in company

Solve now

Problem statement

You just bought a game of monsters which consists of various levels consisting of monsters. Each monster has power ‘P’ associated with it. Each monster follows (‘P’ * ‘P’ + 1) % ‘M’ distinct monsters in the next level having values from 0 to [(‘P’ * ‘P’ + 1) % ‘M’] - 1 where ‘M’ is a modulo integer given to you. Find the total number of monsters in all levels you need to finish to clear the game.

Note :

In the first level, there is only one monster with power, ‘P’ = 2.

Input Format :

The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two single space-separated integers ‘L’ and ‘M’ representing the number of levels and the modulo integer respectively.

Output Format :

For each test case, print a single integer modulo ‘M’ representing the number of monsters. 

Print the output of each test case 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 <= 10
1 <= L <= 10
3 <= M <= 50

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to pre-compute monsters from 0 to ‘M’ levels. Monster at any level cannot be more than ‘M’ since we are using ‘M’ as modulo at each level for the number of monsters. We use a queue to traverse the monsters at each level and push the monsters of a new level into the queue.

Here is the algorithm :

Create a queue (say, ‘Q’) and push 2 (power of the first monster) and -1 (endpoint) into it.
Create a variable (say, ‘COUNT’) that will store the number of monsters and initialize it with 1.
Create an array (say, ‘DP’) that will store the number of monsters for each ‘M’ and initialize it with 0.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) and update ‘DP[i]’ as ((i * i) + 1) % ‘M’.
Run a loop, while ‘L’ is greater than 1
- Run a loop, while the front of ‘Q’ is not equal to -1.
  - Create a variable (say, ‘X’), store the front of ‘Q’ into it, and pop it from ‘Q’.
  - Update ‘COUNT’ as (‘COUNT’ + ‘DP[x]’) % ‘M’.
  - Run a loop from 0 to ‘DP[x]’ (say, iterator ‘i’)
    - Push ‘i’ into ‘Q’.
Pop the front element from ‘Q’.
Push -1 into the ‘Q’.
Decrement level ‘L’ by 1.
Finally, return ‘COUNT’.

Solve now