Sum of Shadows

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Microsoft

Problem statement

You are given an array “balls” denoting the size of each ball. You need to calculate the sum of shadow balls for all the balls present in the array.

For Example : 
arr = {3, 5, 1, 4}
In this example, the shadow of ball 3 -> 1.
The shadow of ball 5 -> 1.
Hence the total number of shadows are 1 + 1 = 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of balls.

The next line contains ‘n’ integers denoting the size of each ball.
Output Format : 
For each test case, print a single integer “ans” denoting the sum of shadow balls for all the balls.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10    
1 <= N <= 5000
1 <= balls[i] <= 10^5

Time limit: 1 sec
Sample Input 1 :
2
4
3 5 9 11
3
7 5 3
Sample Output 1 :
0
3
Explanation For Sample Input 1 :
In the first test case, there is no ball having a shadow ball.
Hence, the answer is 0.

In the second test case, the shadow of ball 7 -> 5, 3 and the shadow of ball 5 -> 3.
Hence the answer is 3.
Sample Input 2 :
2
5
1 5 6 4 20
3
1 2 3
Sample Output 2 :
2
0
Hint

Find all the balls having a size less than the current ball using brute force.

Approaches (3)
Brute Force

In this approach, We will iterate through the array, and for each element of the array, check all the elements with greater index, having a size less than the current element.

The steps are as follows: 

  • Take an integer “answer” to store the final answer.
  • Iterate through the array from 0 to n-1(say iterator be i):
    • Iterate through the array from i+1 to n(say iterator be j):
      • If balls[j] < balls[i], increment “answer”.
      • Else continue.
  • Return “answer”.
Time Complexity

O( N ^ 2 ), where N is the size of the array “balls”.

 

As we are iterating through the array in a nested manner.

Hence the time complexity is O( N ^ 2 ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Sum of Shadows
Full screen
Console