This problem is not very good!


  • -1
    S

    take input 2147395599 as example
    Expect output is 46339 (46339^2-2147395599=-92678)
    but i think 46340 is better (46340^2-2147395599=1)
    and why i can change int sqrt(int x) to int sqrt(float x) without any complie error?

    My code comes from Quake-III Arena

    class Solution {
    public:
        int sqrt(float x) {
        
    	float xhalf = 0.5f*x;
    	int i = *(int*)&x; // get bits for floating VALUE
    	i = 0x5f375a86- (i>>1); // gives initial guess y0
    	x = *(float*)&i; // convert bits BACK to float
    	x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
    	x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
    	x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
    
    	return (int)(abs(1/x));
        }
    };

  • 0
    C

    you should return the floor of actual value;

    input : 8

    return : 2 (not 3)

    because 2*2 < 8


  • 3
    S

    The question is designed for the world of integers (without even taken the decimals into consideration). So you only need to output the integer part.

    As for the Quake III code, it is fast alright, but it is more like a hack. I don't think it is an answer the interviewers look for. First of all, it's basically unexplainable, if the interviewer asks you: "okay... please explain how you came up with this magic number 0x5f375a86", or "can you please show me how this magic number leads to a good initial guess?" how would you respond? Secondly, it shows the interviewer that you are probably one hard-core game programmer, but it does not tell them how much you understand about binary search. Thirdly, you have to remember that number for the interview. So all in all, this is not a practical answer.


Log in to reply
 

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