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

Опубликовано: 22 Сентября, 2022

Для заданного положительного целого числа 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ