Split an array into equal length subsequences consisting of equal elements only
Last Updated :
14 May, 2021
Given an array arr[] of size N, the task is to check if it is possible to split the array arr[] into different subsequences of equal size such that each element of the subsequence are equal. If found to be true, then print "YES". Otherwise, print "NO".
Examples:
Input: arr[] = {1, 2, 3, 4, 4, 3, 2, 1}
Output: YES
Explanation: Possible partition: {1, 1}, {2, 2}, {3, 3}, {4, 4}.
Input: arr[] = {1, 1, 1, 2, 2, 2, 3, 3}
Output: NO
Approach: The idea is based on the following observation: Let the frequency of arr[i] be Ci, then these elements must be broken down into subsequences of X such that Ci % X = 0. This must be YES for every index i. To satisfy this, the value of X should be equal to the greatest common divisor(GCD) of all Ci (1?i?N). If X is greater than 1, then print YES otherwise print NO.
Follow the steps below to solve the problem:
Below is the implementation of the above approach:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the GCD
// of two numbers a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible to
// split the array into equal length subsequences
// such that all elements in the subsequence are equal
void splitArray(int arr[], int N)
{
// Store frequencies of
// array elements
map<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency of arr[i]
mp[arr[i]]++;
}
// Store the GCD of frequencies
// of all array elements
int G = 0;
// Traverse the map
for (auto i : mp) {
// Update GCD
G = gcd(G, i.second);
}
// If the GCD is greater than 1,
// print YES otherwise print NO
if (G > 1)
cout << "YES";
else
cout << "NO";
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4, 4, 3, 2, 1 };
// Store the size of the array
int n = sizeof(arr) / sizeof(arr[0]);
splitArray(arr, n);
return 0;
}
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to find the GCD
// of two numbers a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible to
// split the array into equal length subsequences
// such that all elements in the subsequence are equal
void splitArray(int arr[], int N)
{
// Store frequencies of
// array elements
TreeMap<Integer, Integer> mp
= new TreeMap<Integer, Integer>();
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update frequency of arr[i]
if (mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}
}
// Store the GCD of frequencies
// of all array elements
int G = 0;
// Traverse the map
for (Map.Entry<Integer, Integer> m :
mp.entrySet())
{
// update gcd
Integer i = m.getValue();
G = gcd(G, i.intValue());
}
// If the GCD is greater than 1,
// print YES otherwise print NO
if (G > 1)
System.out.print("YES");
else
System.out.print("NO");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = new int[] { 1, 2, 3, 4, 4, 3, 2, 1 };
// Store the size of the array
int n = arr.length;
new GFG().splitArray(arr, n);
}
}
// This code is contributed by abhishekgiri1
# Python3 program for the above approach
from collections import defaultdict
# Function to find the GCD
# of two numbers a and b
def gcd(a, b):
if (b == 0):
return a
return gcd(b, a % b)
# Function to check if it is possible
# to split the array into equal length
# subsequences such that all elements
# in the subsequence are equal
def splitArray(arr, N):
# Store frequencies of
# array elements
mp = defaultdict(int)
# Traverse the array
for i in range(N):
# Update frequency of arr[i]
mp[arr[i]] += 1
# Store the GCD of frequencies
# of all array elements
G = 0
# Traverse the map
for i in mp:
# Update GCD
G = gcd(G, mp[i])
# If the GCD is greater than 1,
# print YES otherwise print NO
if (G > 1):
print("YES")
else:
print("NO")
# Driver Code
if __name__ == "__main__":
# Given array
arr = [ 1, 2, 3, 4, 4, 3, 2, 1 ]
# Store the size of the array
n = len(arr)
splitArray(arr, n)
# This code is contributed by chitranayal
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to find the GCD
// of two numbers a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is possible to
// split the array into equal length subsequences
// such that all elements in the subsequence are equal
static void splitArray(int[] arr, int n)
{
// Store frequencies of
// array elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Traverse the array
for(int i = 0; i < n; ++i)
{
// Update frequency of
// each array element
if (mp.ContainsKey(arr[i]) == true)
mp[arr[i]] += 1;
else
mp[arr[i]] = 1;
}
// Store the GCD of frequencies
// of all array elements
int G = 0;
// Traverse the map
foreach (KeyValuePair<int, int> i in mp)
{
// Update GCD
G = gcd(G, i.Value);
}
// If the GCD is greater than 1,
// print YES otherwise print NO
if (G > 1)
Console.Write("YES");
else
Console.Write("NO");
}
// Driver Code
public static void Main()
{
// Given array
int[] arr = { 1, 2, 3, 4, 4, 3, 2, 1 };
// Store the size of the array
int n = arr.Length;
splitArray(arr, n);
}
}
// This code is contributed by sanjoy_62.
<script>
// Javascript program for the above approach
// Function to find the GCD
// of two numbers a and b
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if it is
// possible to split the array
// into equal length subsequences
// such that all elements in the
// subsequence are equal
function splitArray(arr, N)
{
// Store frequencies of
// array elements
var mp = new Map();
// Traverse the array
for(var i = 0; i < N; i++)
{
// Update frequency of arr[i]
if (mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.set(arr[i], 1);
}
}
// Store the GCD of frequencies
// of all array elements
var G = 0;
// Traverse the map
mp.forEach((value, key) => {
// Update GCD
G = gcd(G, value);
});
// If the GCD is greater than 1,
// print YES otherwise print NO
if (G > 1)
document.write("YES");
else
document.write("NO");
}
// Driver Code
// Given array
var arr = [ 1, 2, 3, 4, 4, 3, 2, 1 ];
// Store the size of the array
var n = arr.length;
splitArray(arr, n);
// This code is contributed by rutvik_56
</script>
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Similar Reads
Computer Science Subjects