[C] bitwise hashTable, beats 96%


  • 0
    int distributeCandies(int* candies, int candiesSize) {
        // 25,000 blocks with 8 bits in each 
        // are 200,000 bits in total, plus 1 block equals 200,008.
        char hashTable[25001] = {0}, bit;
        int count = 0, halfSize = candiesSize/2,
            index, page, offset;
        
        for(int i = 0; i < candiesSize; i++) {
            index = 100000 + candies[i];
            page = index >> 3;
            offset = index & 7;
            bit = (hashTable[page] >> offset) & 1;
            
            if(bit == 0) {
                count++;
                hashTable[page] |= 1 << offset;
                if( count == halfSize )
                    return count;
            }
        }
        return count;
    }
    

Log in to reply
 

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