LeetCode in Kotlin
3686. Number of Stable Subsequences
Hard
You are given an integer array nums.
A subsequence is stable if it does not contain three consecutive elements with the same parity when the subsequence is read in order (i.e., consecutive inside the subsequence).
Return the number of stable subsequences.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,3,5]
Output: 6
Explanation:
- Stable subsequences are
[1],[3],[5],[1, 3],[1, 5], and[3, 5]. - Subsequence
[1, 3, 5]is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.
Example 2:
Input: nums = [2,3,4,2]
Output: 14
Explanation:
- The only subsequence that is not stable is
[2, 4, 2], which contains three consecutive even numbers. - All other subsequences are stable. Thus, the answer is 14.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Solution
class Solution {
fun countStableSubsequences(nums: IntArray): Int {
var e1: Long = 0
var e2: Long = 0
var o1: Long = 0
var o2: Long = 0
for (x in nums) {
if ((x and 1) == 0) {
val ne1: Long = (e1 + (o1 + o2 + 1)) % MOD
val ne2: Long = (e2 + e1) % MOD
e1 = ne1
e2 = ne2
} else {
val no1: Long = (o1 + (e1 + e2 + 1)) % MOD
val no2: Long = (o2 + o1) % MOD
o1 = no1
o2 = no2
}
}
val ans: Long = (e1 + e2 + o1 + o2) % MOD
return ans.toInt()
}
companion object {
private const val MOD = 1000000007L
}
}