Ninja and Time

Posted: 19 Jun, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

Ninja is sitting for an online examination. He is encountered with a problem with the statement as “For each element in a given array ‘arr’ of integers, find the sum of numbers that have lower index than the current element and are greater than the current number.”

Ninja knows that you are a very good programmer and can help him in solving the problem in a very less amount of time and come up with the most optimized approach to solve the problem. Help Ninja!

Input format :
The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test case contains an integer ‘N’ representing the number of elements in the array.

The second line of each test contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output format :
For each test case, output a single line containing ‘N’ space-separated integers representing the sum of previous greater elements for each element of the array.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5 
1 <= N <= 10 ^ 4
1 <= arr[i] <= 10 ^ 3

Time Limit: 1 sec.
Approach 1

The idea is to calculate the sum of all elements greater than the current element by making nested iterations one to traverse the array and one to check the previous elements for the given condition.

 

Algorithm:

 

  • Make an iteration with an iterator pointer ‘i’ which iterates the whole array.
    • Initialize the variable ‘sum’ to 0 which will store the sum of the previous elements which are greater than the current element.
    • Make an iteration with iterator pointer ‘j’ to for the previous elements from i - 1 to 0 to check for the given condition.
      • If arr[j] > arr[i] then add the value of the element in the ‘sum’.
    • Push the ‘sum’ for the current element in the array, ‘res’.
Try Problem