Skip to main content

Morgan Stanley

Morgan Stanley OA 2022 - Multiply the Subarray Sums

Problem Description:

You are given an array that contains integers in ascending order followed by integers in descending order. All integers in the array are unique and appear only once. Your task is to compute the product of the sum of the values in the ascending part and the sum of the values in the descending part of the array, then return the result modulo (10^9 + 7).

Input Format:

  • The first line contains a single integer N representing the total number of integers in the array.
  • The second line contains N space-separated integers representing the values in the array.

Output Format:

  • Print a single integer representing the product of the sum of the ascending and descending parts of the array, modulo (10^9 + 7).

Constraints:

  • 3 <= N <= 100000
  • 1 <= arr[i] <= 10^9

Sample Input:

7
3 8 14 12 10 7 4

Sample Output:

825

Explanation:

The ascending part of the array is [3, 8, 14], and the sum is 3 + 8 + 14 = 25.
The descending part of the array is [12, 10, 7, 4], and the sum is 12+10+7+4 = 33.
The product of these sums is 25*33 = 825, and since 825 mod (10^9 + 7) = 825, the output is 825.