#3247 - Number of Subsequences with Odd Sum

Medium • View on LeetCode • View on GitHub

Array Dynamic Programming Math Combinatorics

Problem Description

Given an array nums, return the number of subsequences with an odd sum of elements.

Since the answer may be very large, return it modulo 109 + 7.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsequenceCount = function(nums) {
  const MOD = 1e9 + 7;
  let oddCount = 0;
  let evenCount = 1;

  for (const num of nums) {
    if (num % 2 === 1) {
      const newOddCount = (oddCount + evenCount) % MOD;
      const newEvenCount = (evenCount + oddCount) % MOD;
      oddCount = newOddCount;
      evenCount = newEvenCount;
    } else {
      oddCount = (oddCount * 2) % MOD;
      evenCount = (evenCount * 2) % MOD;
    }
  }

  return oddCount;
};