Количество подмножеств, произведение которых кратно уникальным простым числам

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

Для заданного массива arr[] размера N задача состоит в том, чтобы подсчитать количество непустых подмножеств, произведение которых равно P1×P2×P3×……..×Pk , где P1, P2, P3, …….Pk являются различными простыми числами.

Примеры:

Input: arr[ ] = {2, 4, 7, 10}
Output: 5
Explanation: There are a total of 5 subsets whose product is the product of distinct primes.
Subset 1: {2} -> 2
Subset 2: {2, 7} -> 2×7
Subset 3: {7} -> 7
Subset 4: {7, 10} -> 2×5×7
Subset 5: {10} -> 2×5

Input: arr[ ] = {12, 9}
Output: 0

Подход: Основная идея состоит в том, чтобы найти числа, которые являются произведениями только различных простых чисел, и вызвать рекурсию, чтобы либо включить их в подмножество, либо не включить в подмножество. Кроме того, элемент добавляется в подмножество только тогда и только тогда, когда НОД всего подмножества после добавления элемента равен 1. Для решения проблемы выполните следующие шаги:

  • Инициализируйте словарь, скажем, Freq, для хранения частоты элементов массива.
  • Инициализируйте массив, скажем, Unique[] и сохраните все те элементы, которые являются произведениями только различных простых чисел.
  • Вызовите рекурсивную функцию, скажем, Countprime(pos, curSubset) для подсчета всех этих подмножеств.
  • Базовый случай : если pos равен размеру уникального массива:
    • если curSubset пуст, то вернуть 0
    • в противном случае вернуть произведение частот каждого элемента curSubset .
  • Проверьте, может ли элемент в позиции быть взят в текущем подмножестве или нет
    • Если принято, вызовите рекурсивные функции как сумму countPrime(pos+1, curSubset) и countPrime(pos+1, curSubset+[unique[pos]]).
    • в противном случае вызовите countPrime(pos+1, curSubset).
  • Выведите ответ , возвращенный функцией.

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

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

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