Dada una array arr[] y un entero K , la tarea es dividir la array en subconjuntos de tamaño K , de modo que cada subconjunto consta de K elementos consecutivos.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 6, 2, 3, 4, 7, 8}, K = 3
Salida: verdadero
Explicación:
la array dada de longitud 9 se puede dividir en 3 subconjuntos {1, 2 , 3}, {2, 3, 4} y {6, 7, 8} tales que cada subconjunto consta de 3 elementos consecutivos.Entrada: arr[] = [1, 2, 3, 4, 5], K = 4
Salida: falso
Explicación:
la array dada de longitud 5 no se puede dividir en subconjuntos de 4.
Enfoque
Siga los pasos para resolver el problema:
- Almacene las frecuencias de todos los elementos de la array en un HashMap
- Atraviesa el HashMap .
- Para cada elemento presente en HashMap , verifique si todas sus ocurrencias se pueden agrupar en subconjuntos con sus siguientes (K – 1) elementos consecutivos o no. Si es así, reduzca las frecuencias de los elementos incluidos en los subconjuntos en consecuencia en el HashMap y continúe.
- Si se encuentra algún elemento que no se puede agrupar en un subconjunto de K elementos consecutivos, imprima Falso. De lo contrario, imprima True.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
bool groupInKConsecutive(vector<int>& arr,
int K)
{
// Stores the frequencies of
// array elements
map<int, int> count;
for (int h : arr) {
++count[h];
}
// Traverse the map
for (auto c : count) {
int cur = c.first;
int n = c.second;
// Check if all its occurrences can
// be grouped into K subsets
if (n > 0) {
// Traverse next K elements
for (int i = 1; i < K; ++i) {
// If the element is not
// present in the array
if (!count.count(cur + i)) {
return false;
}
count[cur + i] -= n;
// If it cannot be split into
// required number of subsets
if (count[cur + i] < 0)
return false;
}
}
}
return true;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 3, 6, 2,
3, 4, 7, 8 };
int k = 3;
if (groupInKConsecutive(arr, k)) {
cout << "True";
}
else {
cout << "False";
}
}
Java
// Java Program to implement the
// above approach
import java.util.*;
class GFG{
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
static boolean groupInKConsecutive(int[] arr,
int K)
{
// Stores the frequencies of
// array elements
HashMap<Integer,
Integer> count = new HashMap<Integer,
Integer>();
for (int h : arr)
{
if(count.containsKey(h))
count.put(h, count.get(h) + 1);
else
count.put(h, 1);
}
// Traverse the map
for (Map.Entry<Integer,
Integer> c : count.entrySet())
{
int cur = c.getKey();
int n = c.getValue();
// Check if all its occurrences can
// be grouped into K subsets
if (n > 0)
{
// Traverse next K elements
for (int i = 1; i < K; ++i)
{
// If the element is not
// present in the array
if (!count.containsKey(cur + i))
{
return false;
}
count.put(cur + i, count.get(cur + i) - n);
// If it cannot be split into
// required number of subsets
if (count.get(cur + i) < 0)
return false;
}
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 6, 2,
3, 4, 7, 8 };
int k = 3;
if (groupInKConsecutive(arr, k))
{
System.out.print("True");
}
else
{
System.out.print("False");
}
}
}
// This code contributed by sapnasingh4991
Python3
# Python3 program to implement the
# above approach
from collections import defaultdict
# Function to check if a given array can
# be split into subsets of K consecutive
# elements
def groupInKConsecutive(arr, K):
# Stores the frequencies of
# array elements
count = defaultdict(int)
for h in arr:
count[h] += 1
# Traverse the map
for key, value in count.items():
cur = key
n = value
# Check if all its occurrences can
# be grouped into K subsets
if (n > 0):
# Traverse next K elements
for i in range(1, K):
# If the element is not
# present in the array
if ((cur + i) not in count):
return False
count[cur + i] -= n
# If it cannot be split into
# required number of subsets
if (count[cur + i] < 0):
return False
return True
# Driver Code
if __name__ == "__main__":
arr = [ 1, 2, 3, 6, 2,
3, 4, 7, 8 ]
k = 3
if (groupInKConsecutive(arr, k)):
print("True")
else:
print("False")
# This code is contributed by chitranayal
C#
// C# program to implement the
// above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
static bool groupInKConsecutive(int[] arr,
int K)
{
// Stores the frequencies of
// array elements
Dictionary<int,
int> count = new Dictionary<int,
int>();
foreach(int h in arr)
{
if (count.ContainsKey(h))
count[h]++;
else
count[h] = 1;
}
// Traverse the map
foreach(int c in count.Keys.ToList())
{
int cur = c;
int n = count;
// Check if all its occurrences can
// be grouped into K subsets
if (n > 0)
{
// Traverse next K elements
for(int i = 1; i < K; ++i)
{
// If the element is not
// present in the array
if (!count.ContainsKey(cur + i))
{
return false;
}
count[cur + i] -= n;
// If it cannot be split into
// required number of subsets
if (count[cur + i] < 0)
return false;
}
}
}
return true;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 6, 2,
3, 4, 7, 8 };
int k = 3;
if (groupInKConsecutive(arr, k))
{
Console.Write("True");
}
else
{
Console.Write("False");
}
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript Program to implement the
// above approach
// Function to check if a given array can
// be split into subsets of K consecutive
// elements
function groupInKConsecutive(arr, K)
{
// Stores the frequencies of
// array elements
var count = new Map();
arr.forEach(element => {
if(count.has(element))
count.set(element, count.get(element)+1)
else
count.set(element, 1)
});
// Traverse the map
count.forEach((value, key) => {
var cur = key;
var n = value;
// Check if all its occurrences can
// be grouped into K subsets
if (n > 0) {
// Traverse next K elements
for (var i = 1; i < K; ++i) {
// If the element is not
// present in the array
if (!count.has(cur + i)) {
return false;
}
count.set(cur + i, count.get(cur+i)-n);
// If it cannot be split into
// required number of subsets
if (count.get(cur + i) < 0)
return false;
}
}
});
return true;
}
// Driver Code
var arr = [1, 2, 3, 6, 2,
3, 4, 7, 8];
var k = 3;
if (groupInKConsecutive(arr, k)) {
document.write( "True");
}
else {
document.write( "False");
}
</script>
Producción:
True
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)