Cool trick to get naive O(√n) solution Accepted


  • 3
    E

    The simplest solution to code (unless you happen to remember Newton) is likely this one:

        if (x < 2) {
          return x;
        }
        long sqrt = 1;
        while (sqrt * sqrt <= x) {
            sqrt += 1;
        }
        sqrt -= 1;
        return sqrt;
    

    This is O(√n) time and results in Time Limit Exceeded. However, with this little trick you can increase performance up to around 100 times (depending on the tests):

        if (x < 2) {
          return x;
        }
        long sqrt = 1;
        while (sqrt * sqrt <= x) {  /* Copy-paste and set a bigger step */
            sqrt += 100;
        }
        sqrt -= 100;
        while (sqrt * sqrt <= x) {
            sqrt += 1;
        }
        sqrt -= 1;
        return sqrt;
    

    Which is enough to get the naive solution accepted.


Log in to reply
 

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