Given an array arr[] of size N and positive value K, the task is to check whether we can form groups of size K such that elements in the groups are consecutive.
Examples:
Input: N = 9, arr[] = {1, 2, 3, 6, 2, 3, 4, 7, 8}, K = 3
Output:1
Explanation: Groups can be formed of {1, 2, 3}, {2, 3, 4}, {6, 7, 8}.Input: N = 5, arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 0
Explanation: All elements can’t be rearranged to form a group size of 2.
Approach: This can be solved with the following idea:
Using Map data structure, make the smallest element whether see there exist an element with a value greater than 1 until the size of the group becomes K. Once, it becomes, Start again with the smallest element.
Steps involved in the implementation of code:
- Add all elements in the Map data structure.
- Get the smallest element in the map and start forming the group and store it in prev.
- if prev + 1 is present update the prev = prev +1.
- If not, return False.
- Do this until a group of size K is formed.
- Once, formed a group start repeating the second step again.
- If all elements are covered in groups return True, Otherwise, False.
Below is the implementation of the code:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>#include <iostream>using namespace std;// Function to check whether groups of// size L can be formedbool checkGroups(vector<int>& arr, int K){ // If size of array is not // Divisible by K if (arr.size() % K != 0) { return false; } // Initialising Map data structure map<int, int> m; int i = 0; while (i < arr.size()) { m[arr[i]]++; i++; } int len = arr.size(); while (len > 0) { int form = 0; int prev = -1; for (auto a : m) { // Getting smallest // value in map if (prev == -1) { prev = a.first; } else if (prev + 1 == a.first) { prev = a.first; } else { return false; } form++; m[a.first]--; if (m[a.first] == 0) { m.erase(a.first); } // If group of size K is // formed if (form == K) { break; } } if (form != K) { return false; } len -= K; } if (len == 0) { return true; } return false;}// Driver codeint main(){ vector<int> arr = { 1, 2, 3, 6, 2, 3, 4, 7, 8 }; int K = 3; // Function call cout << checkGroups(arr, K); return 0;} |
Java
// Java code for the above approach:import java.util.*;class Main { // Function to check whether groups of // size L can be formed static boolean checkGroups(List<Integer> arr, int K) { // If size of array is not // divisible by K if (arr.size() % K != 0) { return false; } // Initializing HashMap Map<Integer, Integer> map = new HashMap<>(); int i = 0; while (i < arr.size()) { map.put(arr.get(i), map.getOrDefault(arr.get(i), 0) + 1); i++; } int len = arr.size(); while (len > 0) { int form = 0; Integer prev = null; Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, Integer> entry = iterator.next(); int key = entry.getKey(); // Getting the smallest value in the map if (prev == null) { prev = key; } else if (prev + 1 == key) { prev = key; } else { return false; } form++; int count = entry.getValue(); if (count == 1) { iterator.remove(); } else { entry.setValue(count - 1); } // If a group of size K is formed if (form == K) { break; } } if (form != K) { return false; } len -= K; } if (len == 0) { return true; } return false; } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList(1, 2, 3, 6, 2, 3, 4, 7, 8); int K = 3; // Function call System.out.println(checkGroups(arr, K) ? '1': '0'); }} |
Python3
# Python code for the above approach:# Function to check whether groups# of size L can be formeddef checkGroups(arr, K): # If size of array is # not divisible by K if len(arr) % K != 0: return False # Initialising Map m = {} i = 0 while i < len(arr): if arr[i] in m: m[arr[i]] += 1 else: m[arr[i]] = 1 i += 1 len_arr = len(arr) while len_arr > 0: form = 0 prev = -1 for key in sorted(m.keys()): # Getting smallest # value in map if prev == -1: prev = key elif prev + 1 == key: prev = key else: return False form += 1 m[key] -= 1 if m[key] == 0: del m[key] # If group of size # K is formed if form == K: break if form != K: return False len_arr -= K if len_arr == 0: return True return False# Driver codearr = [1, 2, 3, 6, 2, 3, 4, 7, 8]K = 3# Function callprint(1 if checkGroups(arr, K) else 0)# This code is contributed by karthik. |
C#
using System;using System.Collections.Generic;using System.Linq;public class Program{ // Function to check whether groups of size L can be formed public static bool CheckGroups(List<int> arr, int K) { // If size of array is not divisible by K if (arr.Count % K != 0) return false; // Initialising Dictionary (C# equivalent of Python Map) Dictionary<int, int> m = new Dictionary<int, int>(); int i = 0; while (i < arr.Count) { if (m.ContainsKey(arr[i])) m[arr[i]]++; else m[arr[i]] = 1; i++; } int lenArr = arr.Count; while (lenArr > 0) { int form = 0; int prev = -1; foreach (int key in m.Keys.ToList().OrderBy(k => k)) { // Getting smallest value in dictionary if (prev == -1) prev = key; else if (prev + 1 == key) prev = key; else return false; form++; m[key]--; if (m[key] == 0) m.Remove(key); // If group of size K is formed if (form == K) break; } if (form != K) return false; lenArr -= K; } if (lenArr == 0) return true; return false; } public static void Main(string[] args) { List<int> arr = new List<int> { 1, 2, 3, 6, 2, 3, 4, 7, 8 }; int K = 3; // Function call Console.WriteLine(CheckGroups(arr, K) ? 1 : 0); }}// This code is contributed by uomkar369 |
Javascript
<script>// JavaScript code for the above approach// Function to check whether groups// of size L can be formedfunction checkGroups(arr, K) { // If size of array is // not divisible by K if (arr.length % K !== 0) { return false; } // Initialising Map let m = new Map(); let i = 0; while (i < arr.length) { if (m.has(arr[i])) { m.set(arr[i], m.get(arr[i]) + 1); } else { m.set(arr[i], 1); } i++; } let lenArr = arr.length; while (lenArr > 0) { let form = 0; let prev = -1; for (const key of [...m.keys()].sort()) { // Getting smallest // value in map if (prev === -1) { prev = key; } else if (prev + 1 === key) { prev = key; } else { return false; } form++; m.set(key, m.get(key) - 1); if (m.get(key) === 0) { m.delete(key); } // If group of size // K is formed if (form === K) { break; } } if (form !== K) { return false; } lenArr -= K; } if (lenArr === 0) { return true; } return false;}// Driver codelet arr = [1, 2, 3, 6, 2, 3, 4, 7, 8];let K = 3;// Function calldocument.write(checkGroups(arr, K) ? 1 : 0);// This code is contributed by Susobhan Akhuli</script> |
Output
1
Time Complexity : O(N*K)
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!
Share your thoughts in the comments
