Timing Sum

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
18 upvotes
Asked in companies
AmazonSalesforceVMware Inc

Problem statement

‘N’ players are playing an online game and you are given the time in seconds each one requires to finish the game in the form of an array ‘A’. Now, the game requires to form pairs of players such that the total time taken is divisible by 60 seconds. More formally you need to find pairs with indices ( ‘i’ , ‘j’ ) such that ‘i’ < ‘j’ and ( A[i] + A[j] ) is divisible by 60.

Output the total number of valid pairs.

Note that a single player can be a part of multiple pairs.

Example :
N = 5
A = [ 30, 20, 30,40, 100 ]

Explanation : 

The valid pairs are : 

( 30, 30 ) as the sum is 60.
( 20, 40 ) as the sum is 60.
( 20, 100 ) as the sum is 120 which is divisible by 60.

Thus we output 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ denoting the number of piles of stones.

The next line contains ‘N’ integers representing the elements of array ‘A’. ‘A[i]’ denotes the time in seconds required by the ‘ith’ player to finish the game.
Output format :
For each test case, output an integer representing the total valid pairs.

Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i] <= 10^9

Time Limit : 1 sec
Sample Input 1 :
2
3
60 60 60
4
150 20 30 100 
Sample Output 1 :
3
2
Explanation Of Sample Input 1 :
For test case 1 we have,    

There are three pairs with indices ( 1, 2) , ( 1, 3) and ( 2, 3).

So, we output 3.

For test case 2 we have,    

The valid pairs are : 

( 150, 30 ) with sum 180 divisible by 60.
( 20, 100 ) with sum 120 divisible by 60.

So, we output 2.
Sample Input 2 :
2
2 
40 20 
5
30 20 90 40 60 
Sample Output 2 :
1
2
Hint

Stimulate the problem statement.

 

Approaches (2)
Brute Force

 

Approach : 

 

  • The problem statement simply translates to finding pairs ( ‘i’, ‘j’ ) such that ‘i’ < ‘j’ and ( ‘A[i]’ + ‘A[j]’ ) % 60 == 0.
  • So, we run two loops over ‘i’ and ‘j’ and check the valid pairs and return the required result.


 

Algorithm : 
 

  • Initialise a variable ‘ans’ = 0.
  • Run a for loop from ‘i=0’ to ‘i=N-1’.
  • Run a for loop from ‘j=i+1’ to ‘j=N-1’.
    • If ( ‘A[i]’ + ‘A[j]’ ) % 60 == 0 :
    • Increment ‘ans’.
  • Return ‘ans’ as the final result.

 

Time Complexity

O( N^2 ) , where ‘N’ is the size of the array ‘A’.

 

We are checking all pairs of an array of size ‘N’. So, the overall time complexity is O(N^2).
 

Space Complexity

O(1)
 

Constant extra space is required. Hence the overall space complexity is O(1).

 

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