Number of Valid Partitions - Linkedin Online Assessment IIT Kanpur

Problem Preview

"You are given an array a of n positive integers. Partition the array into one or more contiguous segments such that every element belongs to exactly one segment. Let the sum of each segment be computed. A partition is considered valid if the parity (odd/even) of the segment sums alternates between every pair of adjacent segments. In other words, if the segment sums are S1, S2, ..., Sk then for every 1 ≤ i < k, (Si % 2) != (Si+1 % 2) Your task is to determine the number of valid partitions. Since the answer can be large, output it modulo 10^9 + 7. Since the answer can be large, output it modulo 10^9 + 7. ### Input n a1 a2 ... an ### Output Print a single integer — the number of valid partitions modulo 10^9 + 7. ### Example 1 #### Input 4 1 2 3 3 #### Output 2 ### Explanation The valid partitions are: [1,2,3,3] [1,2,3] | [3] [1,2] | [3,3] [1] | [2,3,3] The partition [1] | [2] | [3] | [3] is invalid because the segment sum parities are odd, odd, odd, odd which do not alternate."