Sorted Predecessor Sum

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an array of N integers. Your task is to find the sum of all elements that appear before the original last element in the sorted version of the array.

The process is as follows:

1) Identify the value of the last element in the original, unsorted array. Let's call this the target_element.

2) Sort the entire array in non-decreasing (ascending) order.

3) In the newly sorted array, find the index of the first occurrence of the target_element.

4) Calculate and return the sum of all elements that appear at indices before this index. If the target_element is the first element in the sorted array, this sum will be 0.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of the array.

Output Format:

Print a single integer representing the calculated sum.

Note:

If the input array has fewer than 2 elements, there are no elements before the last one, so the sum is 0.

The sum can be large, so be sure to use a data type that can accommodate it (e.g., long in Java, long long in C++).

Sample Input 1:

8
3 1 4 1 5 9 2 6

Sample Output 1:

Explanation for Sample 1:

1.  The original last element is `6`.
2.  The sorted array is `[1, 1, 2, 3, 4, 5, 6, 9]`.
3.  The first (and only) occurrence of `6` is at index 6.
4.  The sum of elements before index 6 is `1 + 1 + 2 + 3 + 4 + 5 = 16`.

Sample Input 2:

4
10 30 20 5

Sample Output 2:

Explanation for Sample 2:

1.  The original last element is `5`.
2.  The sorted array is `[5, 10, 20, 30]`.
3.  The first occurrence of `5` is at index 0.
4.  There are no elements before index 0, so the sum is 0.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Sorted Predecessor Sum

Console