Last Updated: 19 Jun, 2021

Ninja and Time

Hard

Asked in companies

Solve now

Problem statement

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.

Solve now

Approaches

01 Approach

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’.

Solve now

02 Approach

We can use Binary Indexed Tree to optimize the range sum query.

Algorithm:

Define a Fenwick Tree, ‘Bite[]’ globally.
Initialize ‘Bit[]’ by 0.
Make a function ‘solve()’ to calculate the sum and store the sum with the given conditions in an array,say ‘res’ of integers passing ‘arr’, ‘n’, and ‘res’ as arguments to the function.
- First, calculate the total sum of all the elements present in the ‘Bit’ and store the sum in a variable, say ‘totalSum’.
- Now consider each element of the given array ‘arr’ as the index of Fenwick Tree.
- Now find the sum of elements that are smaller than the current element using values stored in the Fenwick Tree and store it in a variable, say ‘sumNow’.
- To obtain the sum which is strictly greater than the current element and on the left side of the element, subtract ‘sumNow’ from ‘totalSum’ (‘totalSum’ - ‘sumNow’).
- Update the current element in the Fenwick Tree.
- Repeat the steps for all elements of the array ‘arr’.

Solve now