Description
Solutions
Bitonic Partitioning
🤘 INTERN

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.

    Example 1:

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

    Example 2:

    Input:  arr = [1, 2, 3, 4, 3, 2, 1]
    Output: 49
    Explanation:
    n/a
    Constraints:
      1 < n <= 100
      -10^9 <= arr[i] <= 10^9
    Thumbnail 0
    Testcase

    Result
    Case 1

    input:

    output: