Last Updated: 28 Mar, 2021
Split The Array
Easy
Asked in company
You are given an array A of length N, now is it possible to split the array into different subsequences of equal length such that all elements in a subsequence are equal. If it is possible to divide the array into such subsequences of length greater than 1 print “YES” if is not possible print “NO”.
Example: [ 1 1 2 2 3 3 3 3] can be divided into [1 1] [2 2] [3 3] [3 3]
Input Format :
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains the three integers N, length of the array.
The second line of each test case contains N space-separated integers of the array A.
Output Format :
Return the result of each test case in a new line.
Constraints :
1 <= T <= 5
1 <= N <= 3000
1 <= A[i] <= 5000
Where ‘T’ denotes the number of test cases.
Approaches
Explanation:
- The key idea is to create a frequency array of the originally given array.
- Now we know that if the frequency of a number is ‘F’ then we can make subsequences out of it of length ‘L’ where F%L ==0 i.e. we can make all the subsequences of length equal to the factors of the frequency.
- Now since we have to do this for all the elements then we just find the largest common such factor that they have in the frequency array.
- In easy terms, to get the optimal largest length of subsequence array we can create, we just need to find the gcd of all the frequencies in the freq array.
Algorithm:
- Create a frequency array (or a hashmap) ‘freq’ for all the elements in the array.
- Calculate gcd of all the elements in the ‘freq’ array and store it in a variable ‘res’.
- If res (i.e. gcd) equals 1, print “NO” else Print “YES”.