C, Iterative, 4 lines


  • 0
    M

    Search incrementing in exponential leaps is a simple but effective improvement over brute force. Just reset the count back to 1 whenever the value might exceed the square root. Clocks 4mS.

        int y = 2, inc = 32; // 32 is a random pick
        for(y = 2; y <= x/y; y += inc, inc <<= 3)
            inc = ((y + inc) > x / (y + inc)) ? 1 : inc; // reset?
        return x == 0 ? x : y - 1; // handle case 0
    

Log in to reply
 

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