find-all-possible-stable-binary-arrays-ii

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given 3 positive integers <code>num_zeros</code>, <code>num_ones</code>, and <code>limit</code>.

A binary array <code>arr</code> is called stable if:

<ul>
	<li>The number of occurrences of 0 in <code>arr</code> is exactly <code>num_zeros</code>.</li>
	<li>The number of occurrences of 1 in <code>arr</code> is exactly <code>num_ones</code>.</li>
	<li>Each subarray of <code>arr</code> with a size greater than <code>limit</code> must contain at least one occurrence of both 0 and 1.</li>
</ul>

Return an integer denoting the total number of stable binary arrays.

Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: zero = 1, one = 1, limit = 2

Output: 2

Explanation:

The two possible stable binary arrays are <code>[1,0]</code> and <code>[0,1]</code>.
</div>

Example 2:

<div class="example-block">
Input: zero = 1, one = 2, limit = 1

Output: 1

Explanation:

The only possible stable binary array is <code>[1,0,1]</code>.
</div>

Example 3:

<div class="example-block">
Input: zero = 3, one = 3, limit = 2

Output: 14

Explanation:

All the possible stable binary arrays are <code>[0,0,1,0,1,1]</code>, <code>[0,0,1,1,0,1]</code>, <code>[0,1,0,0,1,1]</code>, <code>[0,1,0,1,0,1]</code>, <code>[0,1,0,1,1,0]</code>, <code>[0,1,1,0,0,1]</code>, <code>[0,1,1,0,1,0]</code>, <code>[1,0,0,1,0,1]</code>, <code>[1,0,0,1,1,0]</code>, <code>[1,0,1,0,0,1]</code>, <code>[1,0,1,0,1,0]</code>, <code>[1,0,1,1,0,0]</code>, <code>[1,1,0,0,1,0]</code>, and <code>[1,1,0,1,0,0]</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= zero, one, limit &lt;= 1000</code></li>
</ul>