Найдите 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 Nth(= 10th) 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)