Максимальный размер подмножества, при котором произведение всех элементов подмножества является коэффициентом N

Для заданного целого числа N и массива arr[] , содержащего M целых чисел, задача состоит в том, чтобы найти максимальный размер подмножества, при котором произведение всех элементов подмножества является коэффициентом N.

Примеры:

Input: N = 12, arr[] = {2, 3, 4}
Output: 2
Explaination: The given array 5 subsets such that the product of all elements of the subset is a factor of 12. They are {2}, {3}, {4}, {2, 3} as (2 * 3) = 6, and {3, 4} as (3 * 4) = 12. Therefore, the maximum size of the valid subset is 2.

Input: N = 64, arr[] = {1, 2, 4, 8, 16, 32}
Output: 4

Подход: данная проблема может быть решена с помощью рекурсии путем обхода всех подмножеств данного массива arr[] и отслеживания размера подмножеств так, что N % (произведение элементов подмножества) = 0 . Кроме того, чтобы произведение элементов подмножества было множителем N , все отдельные элементы массива arr[] также должны быть множителем N . Таким образом, вышеуказанная проблема может быть решена с помощью следующих шагов:

• Создайте рекурсивную функцию maximiseSubset() , которая вычисляет максимальный размер требуемого подмножества.
• Если все элементы данного массива arr[] были пройдены, верните 0, что является базовым случаем.
• Перебрать все элементы массива arr[] и, если N % arr[i] = 0 , включить arr[i] в подмножество и рекурсивно вызвать N = N/arr[i] для оставшихся элементов массива.

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

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