Split The Array

Easy
0/40
Average time to solve is 20m
7 upvotes
Asked in company
Apple

Problem statement

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]

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
8
1 1 2 2 3 3 4 4
8
1 1 1 2 2 2 3 3
Sample Output 1 :
YES
NO
Explanation for Sample Input 1 :
For the first test case,
We can make subsequences of length 2:  [1 1] [2 2] [3 3] [4 4] 

For the second test case,
We can make only subsequences of length 1, such that all subsequences are of equal length and all elements of the subsequence are the same.
Sample Input 2 :
3
9
26 49 26 23 49 23 23 26 49 
10
21 47 24 47 27 21 27 32 32 24 
18
1 1 31 31 1 31 1 31 1 31 1 1 31 31 1 1 31 31
Sample Output 2 :
YES
YES
YES
Hint

Find gcd of the frequencies

Approaches (1)
find gcd

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”.
Time Complexity

O( N*log(N) )

  where N is the length of the array

Traversing array is O(N) and find gcd of two elements is O( log(N) ) therefore the time complexity is O(N)

Space Complexity

O(N)

  where N is the length of the array

We are creating a new frequency array that will take O(N) space.

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