Last Updated: 1 Dec, 2021
Timing Sum
Moderate
Asked in companies
‘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.
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
Approaches
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.
Approach :
- Since we are only interested in pairs with sum divisible by 60.
- We can keep the elements as modulo 60 so that every element is now < 60.
- Now, for an element ‘x’ , we must pair it with all ‘y’ such that ‘x’ + ‘y’ = 60.
- So, ‘y’ = 60 - ‘x’.
- So, we maintain a frequency array of size 60 and update the count of each element.
- Now for all ‘x’ from ‘x = 1’ to ‘x = 29’ :
- The number of valid pairs will be ‘freq[ x ] * freq[ 60 - x ]’.
- ‘x=0’ and ‘x=30’ are special cases as they both pair with themselves :
- So, their contribution will be ‘( freq[x] * ( freq[x] - 1) ) / 2’.
- We don’t have to traverse from ‘x=31’ to ‘x=59’ as they will cause duplication of pairs.
Algorithm :
- Initialise a variable ‘ans’ = 0.
- Initialise an array ‘freq’ of size ‘60’.
- Run a for loop from ‘i=0’ to ‘i=N-1’.
- Increment ‘freq[ A[i]%60 ]’ by 1.
- Run a for loop from ‘i=1’ to ‘i=29’.
- Increment ‘ans’ by ‘freq[ i ] * freq[ 60-i ]’.
- Increment ‘ans’ by ‘( freq[0] * ( freq[0] - 1) ) / 2’.
- Increment ‘ans’ by ‘( freq[30] * ( freq[30] - 1) ) / 2’.
- Return ‘ans’ as the final result.
Similar problems