Dada una array arr[] de tamaño N , la tarea es verificar si es posible dividir la array arr[] en diferentes subsecuencias de igual tamaño de modo que cada elemento de la subsecuencia sea igual. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 4, 3, 2, 1}
Salida: SI
Explicación: Posible partición: {1, 1}, {2, 2}, {3, 3}, { 4, 4}.Entrada: arr[] = {1, 1, 1, 2, 2, 2, 3, 3}
Salida: NO
Planteamiento: La idea se basa en la siguiente observación: Sea la frecuencia de arr[i] C i , entonces estos elementos deben descomponerse en subsecuencias de X tales que C i % X = 0 . Esto debe ser SÍ para cada índice i . Para satisfacer esto, el valor de X debe ser igual al máximo común divisor (MCD ) de todos los C i (1≤i≤N) . Si X es mayor que 1, escriba SÍ; de lo contrario, escriba NO.
Siga los pasos a continuación para resolver el problema:
- Cree un hashmap , mp , para almacenar las frecuencias de todos los elementos de la array , arr[] .
- Almacene el máximo común divisor de todas las frecuencias en mp en una variable X .
- Si X es mayor que 1, entonces la respuesta es SÍ.
- De lo contrario, la respuesta es NO.
A continuación se muestra la implementación del enfoque anterior:
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
// 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
# 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#
// 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.
Javascript
<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>
Producción:
YES
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA