Easy bitwise java solution


  • 0
    S
        Map<Integer, Boolean> dp = new HashMap<>();
        int maxChoice;
        
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            maxChoice = maxChoosableInteger;
            int sum = maxChoice * (maxChoice + 1) / 2;
            if (sum < desiredTotal)
                return false;
            return canWin(0, desiredTotal);
        }
        
        public boolean canWin (int takenState, int total) {
            int key = takenState + (total << 21);
            Boolean result = dp.get(key);
            if (result != null)
                return result;
            
            int i;
            boolean win = false;
            for (i=1;i<=maxChoice;i++) {
                if ((takenState & (1 << i)) == 0) {
                    takenState += 1 << i;
                    if (i >= total || !canWin(takenState, total - i))
                        win = true;
                    takenState -= 1 << i;
                    if (win)
                        break;
                }
            }
            dp.put(key, win);
            return win;
        }
    }

Log in to reply
 

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