Find the winner in a game, which consists of two players, who are picking integers off an array and splitting an integer into two of its factors and replacing the new integers on the array. The end point is when no move can be made.
Find the sum of prime factors of all the integers present in the array.
Basically, the number of times an integer from the array can be subdivided is equal to the number of prime factors of the number – 1. So, if we sum this up for all the numbers in the array, we get the total number of moves that can be played in a game and it is fixed for a given array. Depending on whether this number is odd or even, we get the winner of the game.
The number of prime factors of an integer can be calculated offline by making a little modification to the Sieve code - by adding 1 to all the numbers encountered in the inner loop. However, even solutions which calculate the number of prime factors of an integer online in log(n) time will also pass the test cases.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.