Примечания к LeetCode [58]: [Kotlin] Просто и лаконично

Проблема



Ближайшие делители — LeetCode
Сможете ли вы решить этот реальный вопрос на собеседовании? Ближайшие делители. По заданному целому числу найдите два ближайших целых числа в…leetcode.com



Интуиция

Ближайшие делители должны содержать квадратный корень из целевого числа. Таким образом, мы можем найти квадратный корень для num + 2, а затем выполнить цикл от квадратного корня до 2, чтобы найти делители.

Код

import kotlin.math.abs
import kotlin.math.sqrt

class Solution {
    fun closestDivisors(num: Int): IntArray {
        val result = intArrayOf(0, Int.MAX_VALUE)
        val sqrt = sqrt(num.toDouble() + 2).toInt() + 1
        listOf(num + 1, num + 2).forEach { number ->
            for (factor in sqrt downTo 2) {
                if (number % factor == 0) {
                    val remains = number / factor
                    if (abs(remains - factor) < abs(result[0] - result[1])) {
                        result[0] = factor
                        result[1] = remains
                    }
                    break
                }
            }
        }
        return result
    }
}

Анализ сложности

  • Временная сложность: O(sqrt{n})
  • Сложность пространства: O(1)