Arranging Coins

Условие

Дано количество монет n. Необходимо построить лестницу, в которой k-я строка содержит ровно k монет. Верни максимальное количество полных строк, которые можно построить.

Примеры

Input: n = 5

Output: 2

Explanation: Первая строка содержит 1 монету, вторая строка содержит 2 монеты, а третья строка требует 3 монеты, но доступно только 2 монеты. Поэтому можно построить только 2 полные строки.

Input: n = 8

Output: 3

Explanation: Первая строка содержит 1 монету, вторая строка содержит 2 монеты, третья строка содержит 3 монеты, и остается 2 монеты для четвертой строки, которая требует 4 монеты. Поэтому можно построить только 3 полные строки.

Решение

fun arrangeCoins(n: Int): Int {
    var left = 0L
    var right = n.toLong()

    // Используем бинарный поиск для поиска максимального количества полных строк
    while (left <= right) {
        val mid = left + (right - left) / 2
        val coinsNeeded = mid * (mid + 1) / 2  // Количество монет, необходимых для mid строк

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

    return right.toInt()  // Возвращаем максимальное количество полных строк
}

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

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

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

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