FastPrepFastPrep
Problem Brief

Bitonic Partitioning

INTERNOA

Given an array arr of size n (where n <= 100), find the number of ways to partition the array. The elements should be divided into partitions. The goal is to make the representative array bitonic. For each partition, the average of the array represents the partition.

We should have at least 3 partitions to establish first increasing and then decreasing. Additionally, we only consider partitions that are strictly increasing and then strictly decreasing.

For example, if we have an array of length 4, arr = [1, 3, 2, 1], the valid partitionings are:

  • 1 (Avg: 1) | 3 2 (Avg: 2.5) | 1 (Avg: 1)
  • 1 (Avg: 1) | 3 (Avg: 3) | 2 1 (Avg: 1.5)
  • 1 (Avg: 1) | 3 (Avg: 3) | 2 (Avg: 2) | 1 (Avg: 1)

    • In all 3 partitions, the sequence first increases and then decreases.

    1Example 1

    Input
    arr = [1, 3, 2, 1]
    Output
    3
    Explanation
    n/a

    2Example 2

    Input
    arr = [1, 2, 3, 4, 3, 2, 1]
    Output
    49
    Explanation
    n/a

    Constraints

    Limits and guarantees your solution can rely on.

    1 < n <= 100
    -10^9 <= arr[i] <= 10^9
    public int bitonicPartitioning(int[] arr) {
  // write your code here
}
    Input

    arr

    [1, 3, 2, 1]

    Output

    3

    Sign in to submit your solution.