Найдите ряд, до которого в ромбовидном узоре есть не менее K звезд.

Даны два целых числа N и K , где N представляет собой ромбовидный узор с ( 2 * N) -1 рядами, задача состоит в том, чтобы найти индекс первого ряда, до которого в ромбовидном узоре имеется не менее K звезд.

Обратите внимание, что значение K всегда будет иметь определенный ответ.

Примеры :

Input: N = 3 , K = 8
Output: 4
Explanation: The first 4 rows contain a total of 8 stars.
                               *

                              * *

                             * * *

                              * *

                               *
Input: N = 5, K = 5
Output: 3

Наивный подход: данную проблему можно решить, просто перебирая каждую строку и сохраняя подсчет количества звезд в каждой строке. Выведите первые два, где количество звезд превышает K.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(1)

Эффективный подход. Описанный выше подход можно оптимизировать с помощью бинарного поиска по значению количества строк из [0, 2*n-1] . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные start = 0, end = (2 * N) – 1 и, ans = 0.
• Выполните следующие действия, пока значение start меньше конец .
  • Вычислить середину , которая равна (начало + конец) / 2
  • Подсчитайте количество звезд до середины .
  • Если количество звездочек до середины больше или равно K, s разорвет середину в переменную и переместится влево от середины на конец = середина-1
  • В противном случае переместитесь вправо от середины по началу = середина + 1
• Возвратите ans , который является требуемым значением.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log N)
Вспомогательное пространство: O(1)