Time limit: 5000ms
Memory limit: 256mb
Description:
This is an optional problem. You won't lose any marks if you skip it.
In this exercise, for a given array a[], we define the Subarray Sum of an element a[i] as the sum of all elements in a[] that are located to its right and strictly less than a[i].
The total sum of all Subarray Sums for all elements in the array is called the Array Sum. Array Sum of a[] is sum of Subarray Sum from a[0] to a[n-1], n is length of a[].
Given an array a[]. The task is to find the Array Sum of a[]. Consider the a[] = [3, 1, 2], Subarray Sum of a[0] is (1+2)=3, Subarray Sum of a[1] is 0, Subarray Sum of a[2] is 0, Array Sum of a[] is (3+0+0)=0
The main function has been provided. You are required to complete the merge() function which returns the ArraySum of the given array.
Sample Input 1:
4
8 4 2 1
Sample Output 1:
Input the number of integers:
Input these integers:
Array Sum:
11
Explanation: The given array has four Subarray Sums. The Subarray Sum of a[0] is (4+2+1)=7, of a[1] is (2+1)=3, of a[2] is (1)=1, and of a[3] is also (0)=0. Thus, the Array Sum of a[] is the sum of these Subarray Sums, which equals (7+3+1+0)=11.
Sample Input 2:
5
1 2 3 4 5
Sample Output 2:
Input the number of integers:
Input these integers:
Array Sum:
0
Explanation: The given array has five Subarray Sums, all of which are 0. Thus, the Array Sum of a[] is the sum of these Subarray Sums, which equals (0+0+0+0+0)=0.
Code Template:
#include <stdio.h>
#include <stdlib.h>
int merge(int arr[], int temp[], int left, int mid, int right)
{
int SubarraySum = 0;
/*
Fill in your code here.
This function returns the Subarray Sum for the subarray.
*/
return SubarraySum;
}
int mergeSort(int arr[], int temp[], int left, int right)
{
int mid, SubarraySum = 0;
if (right > left) {
mid = (right + left) / 2;
SubarraySum = mergeSort(arr, temp, left, mid);
SubarraySum += mergeSort(arr, temp, mid + 1, right);
SubarraySum += merge(arr, temp, left, mid, right);
}
return SubarraySum;
}
int arraySum(int arr[], int n)
{
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main()
{
int n, *arr;
printf("Input the number of integers:\n");
scanf("%d",&n);
arr = (int*)malloc(sizeof(int)*n);
printf("Input these integers:\n");
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);
printf("Array Sum:\n%d", arraySum(arr, n));
return 0;
}