FastPrepFastPrep
Problem Brief

Array Break

OA

There is an integer array arr of length n. Two arrays b and c are called a perfect break of arr if:

  • The lengths of arrays b and c are n.
  • Elements in array b are in non-decreasing order.
  • Elements in array c are in non-increasing order.
  • They satisfy b[i] ≥ 0, c[i] ≥ 0, and b[i] + c[i] = arr[i], for each i where 0 ≤ i < n.

    • Find the number of possible perfect breaks of arr. Since the number can be large, return the value modulo 1000000007, i.e., (10^9+7).

    Function Description

    Complete the function perfectBreak in the editor.

    perfectBreak has the following parameter:

    int arr[n]: the num of possible perfect breaks modulo (109 + 7).

    1Example 1

    Input
    arr = [2, 3, 2]
    Output
    4
    Explanation
    There are 4 possible perfect breaks of array arr:
  • b = [0, 1, 1], c = [2, 2, 1] is a perfect break because it
    • - b and c have 3 elements - b is non-decreasing order - c is in non-increasing order - elements of b and c are 0 or more than the sums of a[i] + b[i] = [2, 3, 2], which matches arr.
  • b = [0, 1, 2], c = [2, 2, 0] is a perfect break.
  • b = [0, 2, 2], c = [2, 1, 0] is a perfect break.
  • b = [1, 2, 2], c = [1, 1, 0] is a perfect break.
  • b = [1, 3, 2], c = [1, 0, 0] is not a perfect break because b is not non-decreasing.
  • b = [1, 2, 2], c = [2, 1, 0] is not a perfect break because b[0] + c[0] ≠ arr[0].

    • 2Example 2

    Input
    arr = [3, 2]
    Output
    6
    Explanation
    The perfect breaks are: b = [0, 0], c = [3, 2] b = [0, 1], c = [3, 1] b = [0, 2], c = [3, 0] b = [1, 1], c = [2, 1] b = [1, 2], c = [2, 0] b = [2, 2], c = [1, 0]

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 <= n <= 3000
  • 1 <= arr[i] <= 3000
    • public int perfectBreak(int[] arr) {
  // write your code here
}
    Input

    arr

    [2, 3, 2]

    Output

    4

    Sign in to submit your solution.