FastPrepCount Subsequences Without Three Equal-Parity Elements in a Row
Problem · Array

Count Subsequences Without Three Equal-Parity Elements in a Row

Learn this problem
● MediumGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

You are given an integer array nums. Count its non-empty subsequences whose selected order satisfies both rules:

  • No three consecutive selected values are all even.
  • No three consecutive selected values are all odd.

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements. Two subsequences are different when they select different index sets, even if their value sequences are equal.

Return the count modulo 10^9 + 7.

Function

countValidSubsequences(nums: int[]) → int

Examples

Example 1

nums = [1,2,3]return = 7

All seven non-empty subsequences are valid because none contains three consecutive selected values of the same parity.

Example 2

nums = [2,4,6]return = 6

The only invalid subsequence selects all three values, producing a run of three evens. The other six non-empty subsequences are valid.

Example 3

nums = [1,3,5,7]return = 10

Every selected value is odd, so a valid subsequence may contain only one or two elements. There are 4 + 6 = 10 such index sets.

Constraints

  • 1 <= nums.length <= 10^5.
  • 1 <= nums[i] <= 10^9.

More Google problems

drafts saved locally
public int countValidSubsequences(int[] nums) {
  // write your code here
}
nums[1,2,3]
expected7
checking account