Valid Perfect Square

Условие

Дано положительное целое число num. Нужно определить, является ли оно полным квадратом, не используя встроенные функции для вычисления квадратного корня.

Примеры

Input: num = 16

Output: true

Explanation: 4 * 4 = 16, следовательно, 16 — это полный квадрат.

Input: num = 14

Output: false

Explanation: 4 * 4 = 16, следовательно, 16 — это полный квадрат.

Решение

fun isPerfectSquare(num: Int): Boolean {
    var left = 1
    var right = num

    // Используем бинарный поиск, чтобы найти корень
    while (left <= right) {
        val mid = left + (right - left) / 2
        val square = mid.toLong() * mid.toLong()  // Преобразуем в long для избежания переполнения

        when {
            square == num.toLong() -> return true  // Нашли точный квадрат
            square < num -> left = mid + 1  // Ищем в правой половине
            else -> right = mid - 1  // Ищем в левой половине
        }
    }

    return false  // Если не нашли точный квадрат
}

Временная сложность

O(log n), так как используется бинарный поиск.

Пространственная сложность

O(1), так как не используется дополнительная память, зависящая от размера входных данных.