2750. Ways to Split Array Into Good Subarrays
Description
You are given a binary array nums
.
A subarray of an array is good if it contains exactly one element with the value 1
.
Return an integer denoting the number of ways to split the array nums
into good subarrays. As the number may be too large, return it modulo 109 + 7
.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [0,1,0,0,1] Output: 3 Explanation: There are 3 ways to split nums into good subarrays: - [0,1] [0,0,1] - [0,1,0] [0,1] - [0,1,0,0] [1]
Example 2:
Input: nums = [0,1,0] Output: 1 Explanation: There is 1 way to split nums into good subarrays: - [0,1,0]
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 1
Solutions
Solution 1: Multiplication Principle
Based on the problem description, we can draw a dividing line between two $1$s. Assuming the indices of the two $1$s are $j$ and $i$ respectively, then the number of different dividing lines that can be drawn is $i - j$. We find all the pairs of $j$ and $i$ that meet the condition, and then multiply all the $i - j$ together. If no dividing line can be found between two $1$s, it means there are no $1$s in the array, and the answer is $0$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | < |