Last Updated: 18 Nov, 2021

Split Array Into The Subsets

Moderate

Asked in company

Solve now

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.

Print “false” if it is not possible to do the above task.

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.

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

Solve now

Approaches

01 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:

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

Solve now