Subsets With an Odd Total

Medium

You are given an array of positive integers values. Pick a non-empty set of positions and add up the numbers there. How many such sets have an odd total? Two sets that differ in at least one position are counted separately, even if their numbers are equal. Return the answer modulo 10⁹ + 7.

Example 1

values=[3, 4] → 2

[3] and [3, 4] (sum 7) have odd sums. [4] has an even sum.

Example 2

values=[2, 8, 6] → 0

All the numbers are even, so every sum of them is even too.

Example 3

values=[5, 5, 5] → 4

The three single-5 picks and the pick of all three (sum 15) are odd: 4 in total.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 2 · 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Combinatorics

Similar problems

Picks Without a Fixed Gap Medium Sets Without a Fixed Gap Medium Extremes of Small Groups Medium A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard

Input

values=[3, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.