#include <iostream>
using namespace std;
 
int mySqrt(int x) {
	if(x <= 1){
		return x;
	}
	int low = 0, high = x / 2;
	//long to prevent overflow
	long long mid;
	while(low <= high){
		mid = (low + high) / 2;
		//needs to be long to prevent overflow
		long long t = mid * mid;
		//second part is to return floor if x is not perfect square
		if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){
			break;
		} else if(x < t){
			high = mid - 1;
		}else{
			low = mid + 1;
		}
	}
	return mid;
}
 
int main() {
	cout << mySqrt(16) << endl;
	cout << mySqrt(27) << endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG15U3FydChpbnQgeCkgewoJaWYoeCA8PSAxKXsKCQlyZXR1cm4geDsKCX0KCWludCBsb3cgPSAwLCBoaWdoID0geCAvIDI7CgkvL2xvbmcgdG8gcHJldmVudCBvdmVyZmxvdwoJbG9uZyBsb25nIG1pZDsKCXdoaWxlKGxvdyA8PSBoaWdoKXsKCQltaWQgPSAobG93ICsgaGlnaCkgLyAyOwoJCS8vbmVlZHMgdG8gYmUgbG9uZyB0byBwcmV2ZW50IG92ZXJmbG93CgkJbG9uZyBsb25nIHQgPSBtaWQgKiBtaWQ7CgkJLy9zZWNvbmQgcGFydCBpcyB0byByZXR1cm4gZmxvb3IgaWYgeCBpcyBub3QgcGVyZmVjdCBzcXVhcmUKCQlpZiggdCA9PSB4IHx8ICgodCA8IHgpICYmICgobWlkICsgMSkgKiAobWlkICsgMSkgPiB4KSkpewoJCQlicmVhazsKCQl9IGVsc2UgaWYoeCA8IHQpewoJCQloaWdoID0gbWlkIC0gMTsKCQl9ZWxzZXsKCQkJbG93ID0gbWlkICsgMTsKCQl9Cgl9CglyZXR1cm4gbWlkOwp9CgppbnQgbWFpbigpIHsKCWNvdXQgPDwgbXlTcXJ0KDE2KSA8PCBlbmRsOwoJY291dCA8PCBteVNxcnQoMjcpIDw8IGVuZGw7CglyZXR1cm4gMDsKfQ==