Last Updated: 11 Apr, 2021
Ninja And Divisible Array
Moderate
Asked in companies
Ninja has been given an array/list ‘ARR’ of even size ‘N’ and an integer ‘K’. Ninja gives his friend a task to divide the given ‘ARR’ into ‘N’/2 pairs such that the sum of each pair should be divisible by ‘K’.
Can you help Ninja to do this task?
For Example :
If ‘ARR’ = [4 5 6 5 7 3] and ‘K’ = 5
Pairs are(4, 6), (5, 5) ,and (7, 3) and the sum of elements of each pair is divisible by ‘K’ i.e 5.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two single space-separated integers ‘N’ and ‘K’ which represent the size of ‘ARR’ and an integer from which the sum of each pair can be divisible.
The next line contains ‘N’ space-separated integers representing the values of the ‘ARR’.
Output Format :
For each test case, print "true" if Ninja’s friend can divide the ‘ARR’ into two parts according to the above condition else print "false" without quotes.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 50
2 <= ‘N’ <= 10000
1 <= ‘K’ <= 100000
-100000 <= ‘ARR[i]’ <= 100000
Where ‘ARR’[i] represents the value of the ‘ARR’ array/list.
Time limit: 1 sec
Approaches
As we know we have to check if the sum of all ‘ARR’ pairs are divisible by a number ‘K’ or not. To check the sum of elements of a pair is divisible by ‘K’ or not, we are going to add the remainder of each pair and if the remainder is 0 or ‘K’ that means we get the pair.
The steps are as follows:
- Run a loop for ‘i’ = 0 to ‘N’:
- ‘ARR[i]’ = ‘ARR[i]’ % K.
- Declare a HashSet ‘vis’ in which we will store the indexes of the elements which would already be taken to form a required pair.
- Declare a variable ‘j’ and initialize it with 0.
- Run a loop for ‘i’ = 0 to ‘N’:
- If the current index is present in HashSet ‘vis’:
- Continue.
- Run a loop for ‘j’ = 0 to ‘N’:
- If the current index is present in HashSet ‘vis’:
- Continue.
- ‘rem’ = ‘ARR[i]’ + ‘ARR[j]’.
- If ‘rem’ is equal to ‘K’ or 0:
- Add ‘i’ and ‘j’ into the HashSet ‘vis’.
- Break.
- If the current index is present in HashSet ‘vis’:
- If ‘j’ is equal to ‘N’:
- Return false.
- If the current index is present in HashSet ‘vis’:
- If the size of HashSet is equal to ‘N’:
- Return true.
- Else:
- Return false.
As we know we have to check if the sum of all ‘ARR’ pairs are divisible by a number ‘K’ or not. To check the sum of elements of a pair is divisible by ‘K’ or not we have to check this one case.
Case:
If the remainder of the first element of a pair is ‘X’ then the remainder of the second element of the pair should be ‘K’ - ‘X’. Because then only (‘firstEle’ + ‘secondEle’) % ‘K’ = 0.
Proof:
Let’s assume the first element is ‘A’ and the second element is ‘B’.
If A is divided by K and the remainder is X:
A % K = X i.e A = n * K + X
If B is divide by K and the remainder is K - X:
B % K = K - X i.e B = m * K + K - X
Then, add these two equations:
A + B = n * K + m * K + K + X - X => A + B = (m + n + 1) * K => (A + B) % K = 0.
So basically first we have to store the remainder of all numbers in a HashMap ‘freq’ when dividing each number by ‘K’. Then check the frequency of the remainder of a number i.e freq of ‘X’ is equal to the freq of ‘K’ - ‘X’ i.e freq[‘X’] = freq[‘K’ - ‘X’].
And we have to handle some edge cases also:
- When the remainder of a number is 0 i.e the number is completely divisible by ‘K’ i.e ‘X’ = 0
- For this case, both pair remainder frequencies are stored at the same place i.e at ‘freq[0]’. So this value should be even.
- When ‘K’ is even and the remainder of a number is ‘K’ / 2 i.e ‘X’ = ‘K’ / 2 and the remainder of the second element of pair is ‘K’ - ‘X’ => ‘K’ / 2.
- For this case, both pair remainder frequencies are stored at the same place i.e at ‘freq[‘K’ / 2]’. So this value should be even.
- When the number is negative i.e remainder of this number is also negative. So to make this positive we find remainder like this.
- Remainder = A % K + K
The steps are as follows:
- Declare a HashMap ‘freq’ in which we store the frequency of the remainder of each number.
- Run a loop for ‘i’ = 0 to ‘N’:
- ‘rem’ = ‘ARR[i]’ % K + K.
- Add this ‘rem’ into HashMap.
- If the value at key ‘0’ or key ‘K’ / 2 is odd in HashMap
- Return false.
- Iterate through all the values of HashMap:
- If freq[i] != freq[k-1]:
- Return false.
- If freq[i] != freq[k-1]:
- Finally, return true.