Monster Game

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in company
Microsoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 4
1 5
Sample Output 1 :
2
1
Explanation For Sample Input 1 :
For first test case :

Level 1: The number of monsters is 1 with power 2. So the number of monster in next level will be ((2 * 2) + 1) % 4 i.e. 5 % 4 = 1. And the power of next level monster will be from 0 to [((2 * 2) + 1) % 4] - 1 i.e. 0 to 0.
Level 2: The number of monsters is 1 with power 0. 
We reached the last level, so the total number of monsters will be 2.

For second test case :

As there is only 1 level present, so the number of monsters will be 1.
Hint

Think of finding monsters at each level.

Approaches (1)
Brute Force With Pre-computation

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 :

 

  1. Create a queue (say, ‘Q’) and push 2 (power of the first monster) and -1 (endpoint) into it.
  2. Create a variable (say, ‘COUNT’) that will store the number of monsters and initialize it with 1.
  3. Create an array (say, ‘DP’) that will store the number of monsters for each ‘M’ and initialize it with 0.
  4. Run a loop from 0 to ‘M’ (say, iterator ‘i’) and update ‘DP[i]’ as ((i * i) + 1) % ‘M’.
  5. 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’.
  6. Pop the front element from ‘Q’.
  7. Push -1 into the ‘Q’.
  8. Decrement level ‘L’ by 1.
  9. Finally, return ‘COUNT’.
Time Complexity

O(L * M), where ‘L’ is the number of levels and ‘M’ is the given modulo integer.

 

We traverse at each level to count the number of monsters, and at each level, we can have the maximum ‘M’ number of monsters that we traverse using the queue. Therefore, the overall time complexity will be O(L * M).

Space Complexity

O(M), where ‘M’ is the given modulo integer.

 

We use an array of size of ‘M’ to store the number of monsters by doing pre-computation. We also use a queue to store the monsters at each level which can have a maximum ‘M’ size. Therefore, the overall space complexity will be O(M).

Code Solution
(100% EXP penalty)
Monster Game
Full screen
Console