Solution

Method 1 – Count Gaps Between 1s

Intuition

Each split must occur between two 1s, and the number of ways to split is the product of the number of ways to split between each pair of 1s. For each gap of zeros between two 1s, we can split after any of the zeros, so the number of ways is (gap length + 1).

Approach

Find the indices of all 1s in nums.
If there are no 1s, return 0.
For each pair of consecutive 1s, count the number of zeros between them, and multiply (gap + 1) to the answer.
Return the answer modulo 1e9+7.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int numberOfGoodSubarraySplits(vector<int>& nums) {\n        const int MOD = 1e9+7;\n        vector<int> pos;\n        for (int i = 0; i < nums.size(); ++i) if (nums[i] == 1) pos.push_back(i);\n        if (pos.empty()) return 0;\n        long long ans = 1;\n        for (int i = 1; i < pos.size(); ++i) ans = ans * (pos[i] - pos[i-1]) % MOD;\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> numberOfGoodSubarraySplits</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"

Related Tags