Alternative solution: bitwise reconstruction. Fast and simple.


  • 0
    L

    This solution uses the guess API to build the solution bit by bit, starting from the most significant bit.

    // Java/C++ 
    int guessNumber(int n) {
        int number = 0;
        for (int bit = 1 << 30; true; bit >>= 1) {
            switch (guess(bit | number)) {
                case 0: return bit | number;
                case 1: number |= bit; break;
                default: break;
            }
        }
    }
    

    Explanation:

    • Even before the first iteration, iteration 1, it is certain that the first bit (sign) of the target is 0, since the target number is always positive.
    • At the start of each iteration i, the first i bits of number correspond to the first i bits of the target number.
    • At the end of each iteration i, the first i+1 bits of number correspond to the first i+1 bits of the target number.
    • At some point in the loop, bit corresponds to the least significant 1 bit in the target number. At that point the function can return number | bit.
    • This function requires at most a single shift, bitwise-or and assignment per iteration.

    Benchmarks on my machine indicate that this approach is about twice as fast as an equivalent binary search implementation. Using n to determine the starting point of the loop only slowed it down, so I just ignored the parameter.


Log in to reply
 

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