Javascript solution that fits in memory using bitwise operators


  • 1
    C

    Javascript struggles with some of the larger problems here, especially with the size of its Object mapping. I deal with this by storing the state of values that have been used/not-used in a bit array in the used variable, which I access using isUsed(i), setUsed(i), and clearUsed(i). This results in the smallest possible key lengths for the object map.

    This is an extension of one of the top-voted solutions by leogogogo:

    https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation

    var canIWin = function(maxChoosableInteger, desiredTotal) {
        if (desiredTotal <= 0 || maxChoosableInteger >= desiredTotal) return true;
        if ((maxChoosableInteger * (maxChoosableInteger + 1)) / 2 < desiredTotal) return false; // unwinnable 
    
        var gameStates = {},    // hash of used-key => true/false
        used = 0;                      // each bit represents a used value (max 128 bits)
        
        // Our helper function
        var helper = function (runningTotal) {
            if (runningTotal <= 0) return false;
            var key = used;
            if (!gameStates.hasOwnProperty(key)) {
                for (var i = 1; i <= maxChoosableInteger; ++i) {
                    if (!isUsed(i)) {
                        setUsed(i);
                        if (!helper(runningTotal - i)) {
                            gameStates[key] = true;
                            clearUsed(i);    // reset the state of used values
                            return true;        // return true as soon as we find
                                                // a winning combo
                        }
                        clearUsed(i);    // reset the state of used values
                    }
                }
                gameStates[key] = false; // If we make this through the loop without
                                         // returning true, then it's a false
            }
            return gameStates[key];
        };
        
        var isUsed = function (i) {
            return ((used & (1 << (i - 1))) !== 0);
        };
        
        var setUsed = function (i) {
            return used |= (1 << (i - 1));
        };
        
        var clearUsed = function (i) {
            return used &= ~(1 << (i - 1));
        };
        
        return helper(desiredTotal);
    };
    

Log in to reply
 

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