Найдите N-й элемент, распределенный из бесконечных элементов бесконечных типов на основе заданных условий.

Для заданного положительного целого числа N задача состоит в том, чтобы найти N ^-й предмет, выданный, когда существует бесконечное количество предметов бесконечного числа типов, таких, что предметы выдаются следующим образом:

• День 1: Выдается 1 предмет Типа-I.
• День 2: выдаются 2 предмета Типа-II и 1 предмет Типа-I.
• День 3: выдаются 3 предмета Типа-III, 2 предмета Типа-II и 1 предмет Типа-I.
• День 4: выдаются 4 предмета Типа-IV, 3 предмета Типа-III, 2 предмета Типа-II и 1 предмет Типа-I.
• и так далее…

Примеры:

Input: N = 10
Output: 1
Explanation:
Following are the orders of the items given out:

• Day 1: 1 item of Type-I are given out. The sequence is {1}.
• Day 2: 2 items of the Type-II and 1 item of Type-I are given out. The sequence is {1, 2, 2, 1}.
• Day 3: 3 items of the Type-III, 2 items of the Type-II, and 1 item of Type-I are given out. The sequence is {1, 2, 2, 1, 3, 3, 3, 2, 2, 1}.

From the above order of items removed, the N^th(= 10^th) item given out is 1. Therefore, print 1.

Input: N = 399
Output: 11

Подход: Самый простой подход к решению данной проблемы состоит в том, чтобы отслеживать количество дней и подсчет количества предметов, выдаваемых в каждый день, следуя заданному порядку, и печатать тот предмет, который выдается на N ^-й очереди. .

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

Временная сложность: O(N)
Вспомогательное пространство: O(1), так как дополнительное пространство не занято.

Эффективный подход: вышеприведенный подход также можно оптимизировать, используя тот факт, что в данный конкретный день D количество выданных предметов представляет собой сумму чисел от 1 до D, а сумма чисел от дня 1 до этого дня должна быть меньше чем равно N . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные, скажем, count как 0 , чтобы сохранить количество заданных элементов, и день , чтобы сохранить количество элементов за этот день.
• Повторяйте цикл до тех пор, пока значение (count + day*(day + 1))/2 не станет меньше N , и выполните следующие шаги:
  • Добавьте значение day*(day + 1)/2 к переменной count .
  • Увеличьте значение дня на 1 .
• Перебрать диапазон [день, 0], используя тип переменной и выполнив следующие задачи:
  • Добавьте значение type к переменной count .
  • Если значение count больше, чем равно N , то в качестве результирующего ответа выведите значение type .

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

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