FastPrep
Problem · Array

Count Perfect Breaks

Learn this problem
● HardAtlassian logoAtlassianFULLTIMEOA

Problem statement

For a non-negative integer array arr of length n, arrays b and c form a perfect break when both have length n, every value is non-negative, b is non-decreasing, c is non-increasing, and b[i] + c[i] = arr[i] for every index.

Return the number of perfect breaks modulo 1,000,000,007.

Function

countPerfectBreaks(arr: int[]) → int

Examples

Example 1

arr = [2,3,2]return = 4

The four valid non-decreasing arrays b are [0,1,1], [0,1,2], [0,2,2], and [1,2,2]; each determines c = arr - b.

Constraints

  • 1 <= arr.length <= 200000
  • 0 <= arr[i] <= 1000000

More Atlassian problems

drafts saved locally
public int countPerfectBreaks(int[] arr) {
  // Write your code here.
}
arr[2,3,2]
expected4
checking account