Accepted solution using cache


  • 0
    N
    // https://leetcode.com/problems/number-of-1-bits/
    
    var Cache = {};
    
    Cache.get = function(n) {
        return this[n];
    };
    
    Cache.set = function(n, val) {
        this[n] = val;
    };
    
    Cache.has = function(n) {
        return this[n] != null;
    };
    
    var cache = null;
    var bit_slice = 15;
    var mask = 1;
    
    /**
     * @param {number} n - a positive integer
     * @return {number}
     */
    var hammingWeight = function(n) {
        cache = Object.create(Cache);
        
        // Generate map of how may 1s there are in the integer for integers up to bit_slice
        // It's kinda sucks that the cache converts keys to strings
        // Leetcode should support native ES6 Map soon hopefully
        for (i = 0; i <= bit_slice; i += 1) {
            var count = 0;
            var num = i;
            while (num > 0) {
                if ((num & mask) === 1) {
                    count += 1
                }
                num = num >>> 1; // zero fill right shift
            }
    
            cache.set(i, count)
        }
    
        var result = 0;
    
        // Read log2(bit_slice), that is 4 bits, at a time
        while (n > 0) {
            // mask out everything but the last four bits
            var chunk = n & bit_slice;
            result += cache.get(chunk);
            n = n >>> 4; // zero fill right shift
        }
        
        cache = null;
        return result;
    };

Log in to reply
 

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