Number of subsequences with odd sum

Array Math Dynamic Programming Combinatorics

47.0% acceptance

Mar 31, 2026

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

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn subsequence_count(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let odd_count = nums.iter().filter(|&&x| x % 2 != 0).count();
    if odd_count == 0 {
      return 0;
    }
    let n = nums.len();
    let mut result: i64 = 1;
    let mut base: i64 = 2;
    let mut exp = (n - 1) as u64;
    while exp > 0 {
      if exp % 2 == 1 {
        result = result * base % MOD;
      }
      base = base * base % MOD;
      exp /= 2;
    }
    result as i32
  }
}