Ninja and Time

Hard
0/120
Average time to solve is 60m
9 upvotes
Asked in companies
DirectiCodenation

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!

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
8
3 8 5 9 4 7 2 6
4
5 8 4 2
Sample Output 1 :
0 0 8 0 22 17 36 24
0 0 13 17
Explanation for Sample Output 1:
Test case 1:
There is no integer before 3 as it is the first element of the array so the sum of numbers before 3 and greater than 3 is 0.
Sum of numbers before 8 and greater than 8 is 0.
The sum of numbers before 5 and greater than 5 is 8.
The sum of numbers before 9 and greater than 9 is 0.
The sum of numbers before 4 and greater than 4 is 8 + 5 + 9 = 22.
The sum of numbers before 7 and greater than 7 is 8 + 9 = 17.
The sum of numbers before 2 and greater than 2 is 3 + 8 + 5 + 9 + 4 + 7 = 36.
The sum of numbers before 6 and greater than 6 is 8 + 9 + 7 = 24.


Test case 2:
There is no integer before 5 as it is the first element of the array so the sum of numbers before 5 and greater than 5 is 0.
Sum of numbers before 8 and greater than 8 is 0.
Sum of numbers before 4 and greater than 4 is 5 + 8 = 13.
Sum of numbers before 2 and greater than 2 is 5 + 8 + 4 = 17.
Sample Input 2 :
2
3
5 2 10
3
10 2 13
Sample Output 2 :
0 5 0
0 10 0
Hint

Try to think naively by finding the sum of the elements greater than the current element and appearing before the current element in the array.

Approaches (2)
Brute Force

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

O(N ^ 2), where ‘N’ is the length of the given array.

 

As we are making two nested iterations one for iterating the array and one for checking the given condition. Therefore, the overall time complexity will be O(N ^ 2).

Space Complexity

O(1)

 

As we are using constant space for the solution. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja and Time
Full screen
Console