Construct the Rectangle

https://leetcode.com/problems/construct-the-rectangleEasy

Условие

Для данного целого числа area, представляющего площадь прямоугольника, нужно найти целые числа L и W, такие, что:

  1. L * W = area
  1. L >= W
  1. L - W минимально.

Возврати L и W в виде массива [L, W].

Примеры

Input: area = 4

Output: [2, 2]

Explanation: 2 * 2 = 4, и разница между L и W равна 0.
Input: area = 37

Output: [37, 1]
Input: area = 122122

Output: [427, 286]

Решение

fun constructRectangle(area: Int): IntArray {
    var w = 1

    // Определяем начальное значение w как квадратный корень из area без использования библиотечных функций
    while (w * w <= area) {
        w++
    }
    w--  // Уменьшаем на 1, чтобы получить точное значение

    // Находим наибольший возможный делитель w, чтобы L * W = area
    while (area % w != 0) {
        w--
    }

    val l = area / w  // Вычисляем L как целое частное от деления
    return intArrayOf(l, w)
}

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

O(√n), так как мы находим приблизительный квадратный корень area и затем проверяем делимость.

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

O(1), так как возвращаемый массив всегда фиксированного размера [L, W].