Проверьте, существует ли подмножество с суммой равной 1, когда каждый элемент умножается на целое число.

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

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

Примеры:

Input: arr[] = {12, 5, 9, 21}
Output: True
Explanation: Pick numbers 5 and 9. 5*2 + 9*(-1) = 1

Input: arr[] = {9, 29, 6, 10}
Output: True
Explanation: Pick numbers 29 and 10. 29*(-1) + 10*(3) = 1

Подход: если HCF любой пары чисел из массива равен 1 , верните True , иначе False . Уравнение ax + by = 1 имеет решение для x и y , если gcd(a, b) = 1 . Нет необходимости проверять HCF всех возможных пар, поскольку НОД является ассоциативной функцией.

gcd(a0, a1, …, an – 1) = gcd(a0, gcd(a1, …, an-1) = gcd(gcd(a0, a1), gcd(a2, …, an-1)) = …

и так далее, включены все возможные комбинации. Так что просто перебирайте массив, пока не будет найден gcd, равный 1 . В другом мире, если gcd(a0, a1, …, an – 1) = 1, существует подпоследовательность aij с #{ai0, …, aik} = k, 1 <= k <= N , которая дает НОД числа 1 . Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную res как arr[0].
  • Перебрать диапазон [1, N), используя переменную i , и выполнить следующие задачи:
    • Установите значение res как НОД res и arr[i].
    • Если res равно 1, вернуть true.
  • После выполнения вышеуказанных шагов выведите false в качестве ответа.

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

Временная сложность: O (N * log (D)), где D — максимальный элемент в массиве.
Вспомогательное пространство: O(1)

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