Задача: 441. Arranging Coins
У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.
Пример:
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.
👨💻 Алгоритм:
1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.
2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.
3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].
😎 Решение:
class Solution {
function arrangeCoins($n) {
return (int)(sqrt(2 * $n + 0.25) - 0.5);
}
}👉Новости 👉База вопросов