Ninja And Divisible Array

Moderate
0/80
Average time to solve is 15m
2 upvotes
Asked in companies
SAP LabsPayPalAdobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 5
-15 15 
4 20
10 20 30 40
Sample Output 1 :
 true
 true
Explanation of sample input 1 :
In the first test case, there is only 1 pair i.e (-15, 15) and the sum of this pair is 0. 0 is divisible by 5.
In the second test case, pairs are (10, 30) and (20, 40) and the sum of elements of each pair is divisible by ‘K’ i.e 20.
Sample Input 2 :
2
6 2
2 3 4 5 9 7
4 7
10 6 20 4
Sample Output 2 :
 true
 false
Explanation of sample input 2 :
In the first test case, pairs are (2, 4), (3, 7), and (5, 9) and the sum of elements of each pair is divisible by ‘K’ i.e 2.

In the second test case, there is no way to make pairs whose sum is divisible by 7.
Hint

Can you think to solve this by iterating over all combinations of pairs?

Approaches (2)
Brute Force

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:

 

  1. Run a loop for ‘i’ = 0 to ‘N’:
    • ‘ARR[i]’ = ‘ARR[i]’ % K.
  2. Declare a HashSet ‘vis’ in which we will store the indexes of the elements which would already be taken to form a required pair.
  3. Declare a variable ‘j’ and initialize it with 0.
  4. 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  ‘j’ is equal to ‘N’:
      • Return false.
  5. If the size of HashSet is equal to ‘N’:
    • Return true.
  6. Else:
    • Return false.
Time Complexity

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

 

For finding all possible pairs we are iterating over ‘ARR’ using a nested loop. Hence the time complexity is O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the size of ‘ARR’.

 

Because if we find a pair that satisfies the condition which is mentioned above. Then we are adding the indexes of elements involve in this pair into the HashSet ‘vis’. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja And Divisible Array
Full screen
Console