Subarray Last | Practice Problems

Subarray Last

★★★★★

3.6

5 votes

, Math, Basic Math, Observation, C++

Details

Submissions

Discussion

Editorial

Problem

You are given an array $X$ of $N$ integers. We define the $value$ of a subarray as the last element of the subarray. Find the sum of the $value$ of all possible subarrays. A subarray is any contiguous part of the array.

Input Format:

The first line contains an integer $T$ , which denotes the number of test cases.
The first line of each test case contains one integers $N$ denoting the number of elements in the array $X$ .
The second line of each test case contains $N$ integers denoting the elements of $X$ .

Output format:

For each test case, print the sum of the $value$ of all subarrays of the given array $X$ .

Constraints:

$1 <= T <= 10$

$1 <= N <= 10^5$

$1 <= X_i <= 10^5$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case 1:
There are total $3$ subarrays in the given array, i.e. $[\textbf{1}]$ , $[\textbf{3}]$ , and $[1,\textbf{3}]$ . So, the answer is the sum of the last element of all subarrays.
Hence, the answer is $1+3+3=7$ .

For test case 2:
In this case, we can see all elements are equal to $1$ , so the last element of all subarrays of this array will always be equal to $1$ . So, the answer will be equal to the number of subarrays multiplied by $1$ .
Hence, the answer is $4*(4+1)/2 = 10$ .