Question

Given an array of non-negative integers arr , your task is to find the number of ways it can be split into three non-empty contiguous subarrays such that the sum of the elements in the first subarray is less than or equal to the sum of the elements in the second subarray, and the sum of the elements in the second subarray is less than or equal to the sum of the elements in the third subarray.
Note:
• Each element of arr must appear in exactly one of the three contiguous subarrays.
• Although the given numbers are 32-bit integers, the sum of the elements may exceed the limits of the 32-bit integer type. .

Answer 1

Answer:

Here is the C++ program:

#include<iostream>  //to use input output functions

using namespace std;  // to identify objects cin cout

int CountSubArrays(int arr[], int size){   /*function that an array and the size of array as parameters and returns the number of ways it can be split into three non-empty contiguous subarrays such that the sum of the elements in the first subarray is less than or equal to the sum of the elements in the second subarray, and the sum of the elements in the second subarray is less than or equal to the sum of the elements in the third subarray */

   int previous[size];  //stores the sum of previous elements

   previous[0] = arr[0];   //sets the first element of previous array to first element of arr

   for(int i = 1; i < size; i++)  //iterates through the array

previous[i] = previous[i - 1] + arr[i];   //adds the present element i-th element of arr to the previous element of previous array

int next[size];   //to store the sum of next elements

next[size - 1] = arr[size - 1]; //sets the last element of previous array to last element of arr

    for(int i = size ; i >= 0; i--)    //iterates through the array

next[i] = next[i + 1] + arr[i];   //adds the present element i-th element of arr to the next element of next array

int i = 1, j = 1;   //sets two variable to move through the array

int current = 0, count = 0;  

while (i < size - 1 && j < size - 1)  { //moves through the array  

 while (j < size - 1 && current <=previous[i - 1])  {  // updates current array until  it is less than previous[i - 1]

 current += arr[j++];  }   //adds value of current to j-th+1 value of arr

 if (current <= next[j])   {  //if value of current is less than or equal to the j-th value of next  

  count++;    }   //adds 1 to the count and count stores number of ways array can be split

 current -= arr[i++];   }   //decrements current by arr[i++]

return count;  } //returns the number of ways arr can be split into three non-empty contiguous subarrays

int main()  {  //start of main function

int arr[] = {1,2,2,2,5,0};  //declares and assigns values to array arr

int size = sizeof arr / sizeof arr[0]; //computes the size of array arr

cout << (CountSubArrays(arr, size)); }  //calls method by passing arr and size to it in order to find the number of ways it can be split into three non-empty contiguous subarrays

Explanation:

The program generates the previous array sum by adding the present element i-th element of arr to the previous element of previous array

It then generates the next array sum by adding the present element i-th element of arr to the next element of next array

Then two pointers i  and j are declared in order to find the sum of the second subarray.

Then while loop iterates over the array, increments current array with arr[j++] and this loop continues to execute as long as current stays less than previous[i – 1] .

When the current array is greater than or equal to previous[i – 1], then the if condition checks if current array is less than or equal to next[j]. This part basically works for the condition that the sum of the elements in the first subarray is less than or equal to the sum of the elements in the second subarray, and the sum of the elements in the second subarray is less than or equal to the sum of the elements in the third subarray. The value of count is incremented to 1 when the if statement evaluates to true.

Now the current array is decremented by arr[i+1]

The program repeats the above steps and then the function returns the computed value of count.

The output of the program is attached.