# Python MiniMax Bitwise Simple

• Python solution based on MiniMax Strategy. Dic represents whether each state is a Win state or not. If any of the children states are a loose state then the parent state becomes a Win state.
The variable "choices" is the bitwise representation of the choices available. The worst case time complexity should be O(N!) but some pruning has been done to speed up things when possible.

``````def canIWin(self, maxChoosableInteger, desiredTotal):
if desiredTotal==0: return True
if maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal:return False

choices,temp = 0,0
while temp < maxChoosableInteger:
choices |= (1<<temp)
temp +=1

dic ={}
def solve(choice, total):
if (choice,total) in dic: return dic[ (choice,total) ]
if total <= 0: return False
tempChoice,childAns = choice, True
for i in xrange( maxChoosableInteger ):
if tempChoice & 1:
childAns = childAns and solve( choice ^ (1<<i), total-i-1)
tempChoice >>=1
if not tempChoice or not childAns: break

dic[ (choice,total) ] = not childAns
return not childAns

return solve( choices, desiredTotal)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.