Here is The Prime Game problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-prime-game-problem-solution.html

IMPORTANT

There is an issue with the C++ starter code.

The function you are asked to complete takes vector<int> as input but the question stipulates that A[i] is less than 10^18, so int will not do, long is needed. - Change the function input to vector<long>, - Change the code in the main function to read longs using stol() instead of stoi()

This question is well worded (in my opinion) and really rewarding otherwise. If you are stuck, research NIM, the Sprague Grundy function, and XOR.

Always check the specifications :P

This problem is worded very poorly.

For instance: Manasa plays the first move against Sandy. Who will win if both of them play optimally?

Whats optimal? Removing the most balls from a bucket? Removing the ideal number of balls to give the player the best chance of winning?

The example input moves includes both cases......

[Understood and Could Explain] :

A Nim game of n buckets and a[1], a[2], ..., a[n] balls in each bucket cannot be simply divided into n Nim games with 1 bucket and a[1], a[2], ..., a[n] balls in each game. It's not correct to simply XOR all the losses/victories of each bucket to determine the winner of the whole game. i.e. Player who "wins" on even numbers of buckets may not lose the whole game.

For example, consider a game with two buckets and [2, 7] balls respectively. Player 1 "wins" on both buckets but doesn't lose the game. He/She should not take one whole bucket and let the opponent take the other. Instead, the player should take 5 balls from the second bucket, leaving a situation of [2, 2] to the opponent and then win the game.

This is found by finding the grundy/nimber numbers (which was explained by other comments below) and XOR-ing them. The first few grundy numbers for range(11) were [0, 0, 1, 1, 2, 2, 3, 3, 4, 0, 0]. A situation of [2, 7] balls has grundy numbers of [1, 3] for each bucket, and a grundy number of 1 xor 3 == 2 for the whole game. So the player can remove 5 balls from the second bucket, making the remaining situation to have a grundy number of 0, therefore forcing the opponent to lose the game.

Also try [7, 8]. The situation has a grundy number of 3 xor 4 == 7, which does not exist in the grundy numbers list. But the first player can remove 2 balls from the second bucket to change its grundy number from 4 to 3 and wins the whole game.

[Don't Understand, Need Help] :

1. Why do the grundy numbers loop? I mean, since {2, 3, 5, 7, 11, 13} is finite and not the whole set of prime numbers, it's expected to see the grundy numbers to loop with a much longer period, not a short one like this (9).
2. How to find this loop period with code? It's easy to prove that the grundy numbers loop with such a period when you write them down, but not so obvious to let the code to detect it.

For the follow input:

1 10 84 87 78 16 94 36 87 93 50 22

My solution ended with Sandy as the winner, but the test indicates that should be Manasa.

Am I missing something?

Here is my log moves, as the test says to be optimized:

Bucket 0 - 84 Removing 13 left : 71 Removing 13 left : 58 Removing 13 left : 45 Removing 13 left : 32 Removing 13 left : 19 Removing 13 left : 6 Removing 5 left : 1 moves: 7 Bucket 1 - 87 Removing 13 left : 74 Removing 13 left : 61 Removing 13 left : 48 Removing 13 left : 35 Removing 13 left : 22 Removing 11 left : 11 Removing 11 left : 0 moves: 7 Bucket 2 - 78 Removing 13 left : 65 Removing 13 left : 52 Removing 13 left : 39 Removing 13 left : 26 Removing 13 left : 13 Removing 13 left : 0 moves: 6 Bucket 3 - 16 Removing 13 left : 3 Removing 3 left : 0 moves: 2 Bucket 4 - 94 Removing 13 left : 81 Removing 13 left : 68 Removing 13 left : 55 Removing 13 left : 42 Removing 13 left : 29 Removing 13 left : 16 Removing 13 left : 3 Removing 3 left : 0 moves: 8 Bucket 5 - 36 Removing 13 left : 23 Removing 11 left : 12 Removing 11 left : 1 moves: 3 Bucket 6 - 87 Removing 13 left : 74 Removing 13 left : 61 Removing 13 left : 48 Removing 13 left : 35 Removing 13 left : 22 Removing 11 left : 11 Removing 11 left : 0 moves: 7 Bucket 7 - 93 Removing 13 left : 80 Removing 13 left : 67 Removing 13 left : 54 Removing 13 left : 41 Removing 13 left : 28 Removing 13 left : 15 Removing 13 left : 2 Removing 2 left : 0 moves: 8 Bucket 8 - 50 Removing 13 left : 37 Removing 13 left : 24 Removing 13 left : 11 Removing 11 left : 0 moves: 4 Bucket 9 - 22 Removing 11 left : 11 Removing 11 left : 0 moves: 2 final Moves: 54