Hey guys quick question, when solving this issue o...

# announcements

[Nikola Milovic]

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)

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)

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!

[ephemient]

there's no floating point involved in your code at all, neither in Kotlin nor Java

[ephemient]

anyhow integer square root in binary is quite doable just with shifting; no division or multiplication needed:

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
}

[Philip Puffinburger]

I submitted this and it works (based sort of on what you have)

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  
    }

[ephemient]

https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2)

[ephemient]

equivalent to mine, and faster than all those double operations