Given an array arr[] and integer K, the task is to split the array into subsets of size K, such that each subset consists of K consecutive elements.
Examples:
Input: arr[] = {1, 2, 3, 6, 2, 3, 4, 7, 8}, K = 3
Output: true
Explanation:
The given array of length 9 can be split into 3 subsets {1, 2, 3}, {2, 3, 4} and {6, 7, 8} such that each subset consists of 3 consecutive elements.Input: arr[] = [1, 2, 3, 4, 5], K = 4
Output: false
Explanation:
The given array of length 5 cannot be split into subsets of 4.
Approach
Follow the steps to solve the problem:
- Store the frequencies of all array elements in a HashMap
- Traverse the HashMap.
- For every element present in the HashMap, check if all its occurrences can be grouped in a subsets with its next (K – 1) consecutive elements or not. If so, reduce the frequencies of the elements included in the subsets accordingly in the HashMap and proceed forward.
- If any element is found which cannot be grouped into a subset of K consecutive elements, print False. Otherwise print True.
Below is the implementation of the above approach:
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// elementsbool 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 Codeint 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 approachimport java.util.*;class GFG{// Function to check if a given array can// be split into subsets of K consecutive// elementsstatic 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 Codepublic 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 approachfrom collections import defaultdict# Function to check if a given array can# be split into subsets of K consecutive# elementsdef 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 Codeif __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 approachusing 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// elementsstatic 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 Codepublic 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// elementsfunction 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 Codevar 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> |
Output:
True
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
