Hey guys quick question, when solving this issue o...
# announcements
n
Hey guys quick question, when solving this issue on LeetCode using Kotlin https://leetcode.com/problems/valid-perfect-square/ , I am encountering an issue related to Ints and Doubles and I cant seem to solve it. (the question itself is simple) So this is the Kotlin version (this doesnt, infinite loop)
Copy code
fun isPerfectSquare(num: Int): Boolean {
var l = 1
var r = num

while (l <= r) {
val mid: Long = (l + (r - l) / 2).toLong()
if (mid == num.toLong() / mid) { // here is where the problem is as 19/4 gives 4 instead of 4.75
return true
} else if (mid < num.toLong() / mid) {
l = mid.toInt() + 1
} else {
r = mid.toInt() - 1
}

}

return false
}
And the Java version (this one works)
Copy code
public boolean isPerfectSquare(int num) {
int low = 1, high = num;
while (low <= high) {
long mid = (low + high) >>> 1;
if (mid * mid == num) {
return true;
} else if (mid * mid < num) {
low = (int) mid + 1;
} else {
high = (int) mid - 1;
}
}
return false;
}
Basically the issue is, how to keep the floating precision in this example? I've encountered this problem a couple of times now. Try the Kotlin solution with 19 as input Thanks!
e
there's no floating point involved in your code at all, neither in Kotlin nor Java
anyhow integer square root in binary is quite doable just with shifting; no division or multiplication needed:
Copy code
private fun isqrt(num: Int): Int {
var x = 0
var y = num
for (i in Int.SIZE_BITS / 2 - 1 downTo 0) {
val d = 1.shl(i shl 1) + x.shl(i + 1)
if (d <= y) {
x = x or 1.shl(i)
y -= d
}
}
return x
}
p
I submitted this and it works (based sort of on what you have)
Copy code
fun isPerfectSquare(num: Int): Boolean {
var low = 1
var high = num
while (low <= high) {
val mid = ((low + high) ushr 1).toDouble()
when {
mid == num / mid -> {
return true
}
mid < num / mid -> {
low = mid.toInt() + 1
}
else -> {
high = mid.toInt() - 1
}
}
}
return false
}
equivalent to mine, and faster than all those double operations