Max subarray

You are given an array *arr *of length *N*, which contains only two values either *0 * or *1*.

You have to divide the array into maximum number of contiguous subarrays satisfying the following conditions:

- The first subarray should be of length 1. Next subsequent subarrays should have length 1 more than the length of the previous subarray.
- The count of distinct elements in any subarray should be 1.

To achieve the above conditions you can remove zero or more elements from the given array or rearrange the elements (if required). Let *K* be the maximum number of contiguous subarrays that can be formed from the given array satisfying the above conditions after removing (possibly 0) minimum possible elements.

**Task**

Determine the count of distinct obtainable arrangements of the given array such that it satisfies the given conditions and the number of subarrays in that arrangement should be exactly *K*.

*Notes*

- Let us understand the meaning of contiguous subarray with respect to this problem with an example. Suppose after removing minimum possible array elements you get an array of size
*10*. Now, you can rearrange the array elements and divide it into contiguous subarray, i.e.*[ [1], [2, 3], [4, 5, 6], [7, 8, 9, 10] ]*. Here*10*array elements are divided into*4*contiguous subarrays. - Since the answer can be very large print
*answer modulo \(10^9+7\)*.

**Example**

*Assumptions*

*N = 4**arr = [0, 1, 0, 1]*

*Approach*

There are two possible ways to get the *K = 2 *maximum contiguous subarrays:

*[0, 1, 1]:*Remove one*1*from*arr*and rearrange the elements. We can see it is divided into*K = 2*as*[[0], [1, 1]].**[1, 0, 0]:*Remove one*0*from*arr*and rearrange the elements. We can see it is divided into*K = 2*as*[[1], [0, 0]].*

Thus, the answer is *2*.

**Function description**

Complete the function *solve *provided in the editor. This function takes the following *2 *parameters and returns the required answer:

*N:*Represents the size of array*arr**arr:*Represents the elements of array*arr*

**Input format**

**Note**: This is the input format that you must use to provide custom input (available above the **Compile and Test **button).

- The first line contains
*T*denoting*T*also specifies the number of times you have to run the*solve*function on a different set of inputs. - For each test case:
- The first line contains
*N*denoting the size of array*arr.* - The second line contains
*N*space-separated value either*0*or*1*, denoting the elements of*arr*.

- The first line contains

**Output format**

For each test case, print the answer *modulo* \(10^9+7\) in a new line.

**Constraints
\(1 \leq T \leq 10\)
\(1 \leq N \le 10^5\)**

\(arr_i \in \{0, 1\} \space \forall \space i\in[1, N]\)

**Code snippets (also called starter code/boilerplate code)**

This question has code snippets for C, CPP, Java, and Python.

Sample Input

(Plaintext Link)
2 2 0 1 6 0 1 0 1 0 1

Sample Output

(Plaintext Link)
2 2

Explanation

The first line denotes *T = 2.*

**The first test case**

*Given*

*N = 2**arr = [0, 1]*

*Approach*

You can make maximum *1* subarray (*K = 1)* that can satisfy the given conditions.

There are two possibilities:

*[0]:*Remove one*1*from*arr*and get the corresponding array.*[1]:*Remove one*0*from*arr*and get the corresponding array.

*K = 2 *and higher values are not possible since the array *arr *has only 2 elements.

Thus, the answer is 2.

**The second test case**

*Given*

*N = 6**arr = [0, 1, 0, 1, 0, 1]*

*Approach*

You can make maximum *3* contiguous subarrays (*K = 3)* that can satisfy the given conditions.

There are two possibilities:

*[0, 0, 0, 1, 1, 1]:*Rearrange the elements of*arr*to get the corresponding array. We can see*K = 3*since the array can be divided as*[[0], [0, 0], [1, 1, 1]].**[1, 1, 1, 0, 0, 0]:*Rearrange the elements of*arr*to get the corresponding array. We can see*K = 3*since the array can be divided as*[[1], [1, 1], [0, 0, 0]].*

*K = 4 *and higher values are not possible since the array *arr *has only 6 elements.

Thus, the answer is *2*.

Time Limit:
5.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Score is assigned if any testcase passes.

Allowed languages:
Bash,
C,
C++,
C++14,
C++17,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
Java 14,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
Python 3.8,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift-4.1,
Swift,
TypeScript,
Visual Basic

Login/Signup to Run Your Code
You must save any code that is already written. After you login, we will automatically save your code.

Initializing Code Editor...