Split Array Into The Subsets

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in company
Adobe

Problem statement

Given an array, 'ARR' of 'N' integers print “true” if it is possible to split the array into some finite number of subsets such that each subset has the same integer in it and all subsets have the same size. The size of the subset should be greater than one.

Example: 
Input: 'ARR' = [1, 2, 4, 4, 1, 2]
Output: true

We can split the above array like this: [1, 1], [4, 4], [2, 2]

In the three subsets, each of size two. And every subset contains the same elements.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

The first line of each test case contains a single integer 'N' size of the input array ‘ARR’. The second line contains 'N' integers the array elements.
Output format : 
For each test case, print "true" if it is possible to split the array else print "false".

Output for each 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’ <= 10
1 <= 'N' <= 10^5
-10^9 <= 'ARR[i]'<= 10^9

Time Limit : 1 sec
Sample Input 1 :
2
6
2 2 4 5 4 5
5
4 3 5 6 3
Sample Output 1 :
true
false
Explanation Of Sample Input 1 :
For the first test case, we can split the array like this: [2, 2], [4, 4], [5, 5].

For the second test case, it is not possible to split the array with the given condition.
Sample Input 2 :
2
6
2 3 4 5 3 5
9
2 3 3 2 3 1 2 1 1
Sample Output 2 :
false
true
Hint

Try to think of counting the frequency of every number in the array.

Approaches (1)
Brute Force approach

Approach: 

 

We can easily solve this problem by counting the frequency of every number of the array using a hashmap, and then we can form the groups according to the gcd of frequency count.

If the gcd is one then it is not possible to split the array, else it is possible.

 

Algorithm:

  1. If size of the array is 1, then we cannot meet the required condition.
    • So, return false.
  2. Initialize hashmap 'frequencies' to store the frequency of every element of the array.
  3. Iterate over the array and update the count for every element in the hashmap.
  4. Initialize the variable 'gcdOfAll' with frequency count of first element of the array.
  5. Run a loop ‘i’ from 1 to ‘N’:
    • Update ‘gcdOfAll’ with the GCD of ‘gcdOfAll’ and ‘frequencies[ARR[i]]’.
  6. If 'gcdOfAll' is equal to 1, then return false.
  7. Return true.
Time Complexity

O(N * Log(N) * Log(N)), where 'N' is the length of the input array 'ARR'.

 

Since we are using hashmap for every key insertion and updation, it will take Log(N) complexity. Also, simultaneously we are looping over the whole array of size 'N' and calculating the gcd, the gcd operation will take another Log(N) time; hence the overall time complexity will be O(N * Log(N) * Log(N)).

Space Complexity

O(N), where 'N' is the length of the input array 'ARR'.

 

In the worst-case Map can contain 'N' key-value pairs. Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Split Array Into The Subsets
Full screen
Console