More Knowledge acquired when we continue improving the solution ^_^


  • 1
    D

    This is a nice brainteaser introduced by Leetcode. Below is a fast method to find integer square root (Credited to stackoverflow)

       public class Solution {
        public int bulbSwitch(int n) {
            return isqrt(n);
        }
        public int isqrt(int n){
            long op  = n;
            long res = 0;
            long one = 1 << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type
        
        
            // "one" starts at the highest power of four <= than the argument.
            while (one > op)
            {
                one >>= 2;
            }
        
            while (one != 0)
            {
                if (op >= res + one)
                {
                    op = op - (res + one);
                    res = res +  2 * one;
                }
                res >>= 1;
                one >>= 2;
            }
            return (int) res;
        }
    }
    

    PS: Apparently, we've learned more than if we stopped at just using (int) Math.sqrt(n).


  • 0

    I don't see how that's an improvement. It's complicated, it's error-prone (in fact it's wrong, for example for n=2000000000), and it's slower.


  • 0
    D

    I'm not saying that that is an improvement. My point is just: what knowledge we get if we don't satisfied using the built-in methods. We will understand the behind screen theories such as babylonian, newton's method.etc. For examples, there are more algorithms for finding sqrt . The method above might be slower than Math.sqrt, it is because it is designed to some embedded system, not floating point hardware. The other reason maybe because Math.sqrt calls the native method sqrt. And also, Ive modified the code for it to work with larger int.


  • 0

    Well I'd say your title "... improving the solution*"* does mean that it's (supposedly) an improvement.

    We btw also have integer square root as a problem here at leetcode, so no need to develop it in other problems as well. Once is enough. At least for me :-)


Log in to reply
 

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