Создайте самый длинный массив, начинающийся с N и A[i] как кратный A[i+1]

Учитывая целое число N , задача состоит в том, чтобы построить максимально длинный массив A[], такой, чтобы выполнялись следующие условия:

• А[0] = Н.
• Никакие два соседних элемента не должны быть равными.
• Для всех i (0 < i < длина массива), таких, что A[i] делится на A[i + 1]

Примечание: если возможных последовательностей много, выведите любую последовательность.

Примеры:

Input: N = 10
Output: 3,  {10, 2, 1}
Explanation: The maximum possible length of the array A[] is 3 
which is {10, 2, 1}, Thus no bigger array is possible for N = 10.

Input: N = 8
Output: 4,  {8, 4, 2, 1}

Подход: Интуиция для решения этой проблемы и максимизации длины последовательности такова:

For each element simply find the highest divisor (apart from the number itself) of the previous number which in return will have maximum number of divisors possible.

Следуйте иллюстрации ниже для лучшего понимания.

Иллюстрация:

Consider N = 8;

•   N = 8, highest divisor = 4
  •   So, in next step N = 4
•   N = 4, highest divisor = 2
  •   So, in next step N = 2
•   N = 2, highest divisor = 1
•   Here, the base condition is reached thus, stop.

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

• Запустите цикл, пока N не станет больше 1
  • Найдите все делители числа.
  • Присвоить максимальный делитель числа N
• В последнем нажмите 1 в результирующий массив.

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

Временная сложность: O (log ₂ N * Sqrt (M))
Вспомогательное пространство: O(log ₂ N * M), где M — количество делителей, а logN — количество запусков цикла.