Max subarray

You are given an array arr of length N, which contains only two values either 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 the number of test cases. 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.

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...
Notifications
View All Notifications

?