Count Subsequences Without Three Equal-Parity Elements in a Row
Updated
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[]) → intExamples
Example 1
nums = [1,2,3]return = 7All seven non-empty subsequences are valid because none contains three consecutive selected values of the same parity.
Example 2
nums = [2,4,6]return = 6The 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 = 10Every 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 Online Assessment questions
- Book Reading EveningsOA · Seen Nov 2026
- Count Score CategoriesOA · Seen Nov 2026
- Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Shortest Path in a Binary MatrixOA · Seen Nov 2026
- Robot Assembly Line ConflictsOA · Seen Oct 2026
- Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Biggest Number From DigitsOA · Seen Oct 2026
- Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
- Decreasing SubsequencesOA · Seen Sep 2026
- Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026
Similar questions at other companies
- Count Strictly Increasing Subsequences of Length 3IBM · OAIBM interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Pressure-Isolation Shutdown OrderIntuit · OAIntuit interview questions
- Count Good SubsequencesFlexport · OAFlexport interview questions
- Sum of Compressed Number for All SubarraysWells Fargo · OAWells Fargo interview questions
- Count Perfect BreaksAtlassian · OAAtlassian interview questions
- Winning Draws for a Mahjong HandZip · PHONE SCREENZip interview questions
- Coin Change IIApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
- 0/1 KnapsackConfluent · OAConfluent interview questions
- Count Overlapping Square PairsRamp · OARamp interview questions