I did not see anything in the problem statement that the tower has to be broken into prime numbers first. Where is that from? thanks

!/bin/python3

import os import sys import math #

Complete the towerBreakers function below.

# def towerBreakers(arr): # # Write your code here. # d=0 for x in arr: d^=primeFactors(x) if(d!=0): return 1 else: return 2

def primeFactors(n): count=0 flag= True while n % 2 == 0: if(flag): count+=1 flag=False n = n / 2 for i in range(3,int(math.sqrt(n))+1,2): while n % i== 0: count+=1 n = n / i
if n > 2: count+=1 return count

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input())

for t_itr in range(t):
    arr_count = int(input())

    arr = list(map(int, input().rstrip().split()))

    result = towerBreakers(arr)

    fptr.write(str(result) + '\n')

fptr.close()

My Code with comments : https://github.com/offamitkumar/HackerRank/blob/master/Algorithms/Game%20Theory/Tower%20Breaker%2C%20Again.cpp

Assuming you know very well about finding grandy value of every state . Now think about , a normal number 105 .

Its all divisors are

1, 3, 5, 7, 15, 21, 35, 105

So , Our tower with height(105) can be broken into 105/Z=35(Y) towers with all have equal size Z=3 . So grandy value of a state is the mex of all the possible states which can be reached by a valid move (mex is the minimum state that is not possible to be reached from that particular state ) .

Here , when we will break a tower (105) into 35(Y) towers with size of all 3(Z) .Then the grandy value of (105) will be G(105).

Where G(105) will be xor of all other grandy value of child towers of this father tower .

G(105) = G(3) ^ G(3)^G(3)^G(3)......... till 35(Y) times . But we can easily catch that if Y is odd then no need to xor of all Z . It will be obviously only G(3) as rest of all are even in number ( canceled out by the xor ) .

So , G(105)= G(3) when , we will break it into 35(Y) towers with size of all 3(Z) only and not take other possible state's grandy vale .

But we can break it into its all divisors according to question . More fromally ,we have to take into account all possible state's grandy value .So use sieve to calculate all divisors of a number till 100000 previously. Now according to question grandy of (105) will be mex of the set { G(1), G(3),G( 5), G(7), G(15), G(21), G(35),G( 105 ) } and another fact is when Y will be even for any Z ,then Xor will be zero i.e. G(Z) =0 . I hope all are clear . My pseudocode to find grandy recursively

 `int sg(int X)
{
    if(X==1)/// when the
    {
        return 0;
    }
    if(grandy[X]!=-1)/// if grandy value is already computed just return it , no need to calculate it
    {
        return grandy[X];
    }
    set<int>s;
    for(int i=0;i<divisors[X].size();i++)
    {
        int Y=divisors[X][i];/// the tower will be broken down into Y towers ,Y>1
        /// 1 is not included into any number's list of divisors during sieve ,so this Y will not be 1 never
        int Z=X/Y;/// Each of Y towers has height of Z , may be also height of 1 which will terminate our program by finding our grandy value of every X,as X=1 is base condition .
        if(Y%2==0) /// The number of towers are even then ,obviously its all tower's size will be canceled out as being of equal,grandy value will be 0 .
            s.insert(0);
        else  /// The number of towers are odd,obviously take only grandy value of one tower's size (Z).rest of the towers are canceled out by each other for xor technique.
            s.insert(sg(Z));
    }
    int mex=0;
    while(s.find(mex)!=s.end()) mex++;///checking which smallest number not included in the set.
    grandy[X]=mex;///assigning mex[not included minimum element in the set of grandy value of possible towers]
    return grandy[X];/// return grandy
}`

My full solution here :- https://github.com/joy-mollick/Game-Theory-Problems/blob/master/HackerRank-Tower%20Breakers%2C%20Again!.cpp

should

"assuming both players always move optimally?"

I'm guessing 'optimally' here is not to end the game the quickest, ie each player converts the towers higher then or equal to 2 into the same number of towers of height 1 in turns. 'optimally' actually means, each player needs ensure the longevity of each game and break the towers into largest hights possible within the given rules.