Количество подпоследовательностей с суммой на два меньше суммы массива

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

Дан массив vec[] размера N неотрицательных целых чисел. Задача состоит в том, чтобы подсчитать количество подпоследовательностей с суммой, равной S – 2 , где S – сумма всех элементов массива.

Примеры:

Input: vec[] = {2, 0, 1, 2, 1}, N=5
Output: 6
Explanation: {2, 0, 1, 1}, {2, 1, 1}, {2, 0, 2}, {2, 2}, {0, 1, 2, 1}, {1, 2, 1}

Input: vec[] = {2, 0, 2, 3, 1}, N=5
Output: 4
Explanation: {2, 0, 3, 1}, {2, 3, 1}, {0, 2, 3, 1}, {2, 3, 1}

Наивный подход: идея состоит в том, чтобы сгенерировать все подпоследовательности и проверить, равна ли сумма каждой отдельной подпоследовательности S-2 или нет.

Ниже приведена реализация описанного выше подхода.

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

Эффективный подход: идея состоит в том, чтобы использовать комбинаторику, которая, кроме 0, 1 и 2 , все остальные элементы в нашем массиве будут частью желаемых подпоследовательностей. Назовем их дополнительными элементами. Затем подсчитайте количество вхождений 0, 1 и 2 в массиве. Допустим, количество нулей равно x , количество единиц равно y , количество двоек равно z .

  • Let’s count the number of desired subsequences if all 2’s and extra elements are in the subsequence. Now there can be exactly y – 2 elements out of y. Note that there is no restriction for taking 0’s as it contributes nothing to our subsequence sum.
  • Hence, the total count of such subsequences = count1 = 2x × yCy – 2  = 2x × yC2 ( Since, nC0 + nC1 + . . . + nCn  = 2n).
  • Let’s count the number of subsequences if all the 1’s are in our subsequence. Now there can be exactly z – 1 elements out of z.
  • Hence, the total count of such subsequences = count2 = 2x  × zCz – 1 = 2x  ×   zC1
  • Total count of subsequences whose sum is equal to S – 2, count = count1 + count2 = 2x × ( yC2 + zC1 )

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную sum как сумму массива.
  • Инициализируйте переменную answer как 0 , чтобы сохранить ответ.
  • Инициализируйте переменные countOfZero, countOfOne и countOfTwo для хранения количества 0, 1 и 2.
  • Пройдите массив vec[] с помощью итератора x и выполните следующие задачи:
    • Подсчитайте количество вхождений 0, 1 и 2.
  • Инициализируйте переменные value1 как 2 countOfZero .
  • Инициализируйте переменную value2 как (countOfOne * (countOfOne — 1)) / 2 .
  • Инициализируйте переменную value3 как countOfTwo.
  • Установите значение ответа как значение1 * (значение2 + значение).
  • После выполнения вышеуказанных шагов выведите значение answer в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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

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