LeetCode OJ - Sqrt(x) (try 9 times)

為了練習尋找實習時會碰到的問題，我用別人推薦的 LeetCode online judge。
希望能直接寫程式，不用事先編譯就能直接AC。

To practice future interview question, I use LeetCode online judge.
I am trying to type code directly on website without compile in other tool.

編譯錯誤次數 Compile Error number: 0
嘗試次數 Try number:  13 (AC:1) (WA: 2) (TLE: 6)
是否事先在其他工具編譯 if compile first in other tool: No

使用的程式語言 using programming language: C++
以前是否看過 seen this problem before: No

點這裡看題目 Click here to see this Problem!

TLE/WA: 要注意，因為INT_MAX是end, mid*mid有可能會overflow,
我是用 long long 解決，或是一開始就把 end的最大值設為 sqrt(INT_MAX) (這應該是固定直，所以應該可以)

	class Solution {
	public:
	int sqrt(int x) {
	//use binary search to find answer, the bound is from 0 to maximun integer
	int end = INT_MAX;
	int beg = 0;
	int mid = (beg + end) / 2;
	while(beg <= end){
	long long int tmp = (long long)mid * (long long)mid;//in case the mid*mid will overflow
	if( tmp == x )//find sqrt answer
	return mid;
	else if( tmp > x)//mid is too large
	end = mid - 1;
	else //mid*mid < x -> mid is too small
	beg = mid + 1;
	mid = (beg + end)/2;
	}
	return mid;
	}
	};

view raw leecode OJ Sqrt(x).cpp hosted with ❤ by GitHub

If you want to use (copy, paste or quote) my original article, please contact me through email. (autek.roy@gmail.com) If there is any mistake or comment, please let me know. :D

如要使用(複製貼上或轉載)作者原創文章， 請來信跟我聯絡。(autek.roy@gmail.com) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )