Last Updated: 10 Mar, 2021

Divide Array In K Sets Of Consecutive Numbers

Moderate

Asked in companies

Solve now

Problem statement

Given an array of integers ‘ARR’ and a positive integer ‘K’, find whether it's possible to divide this array into sets of 'K' consecutive numbers.

Example:

Let’s say we have an array {1, 2, 3, 6, 2, 3, 4, 7, 8} and integer K = 3.

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 format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two integers ‘N’ and ‘K’ where ‘N’ denotes the number of elements present in the array and ‘K’ denotes the size of each subset in which the array has to be divided so that it contains ‘K’ consecutive elements.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, print a single line containing "True" or "False" depending on whether the array can be divided into ‘K’ sized subsets with 'K' consecutive elements.

The output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= K <= N <=  5 * 10 ^ 4
1 <= ARR[i] <= 10 ^ 9

Where ‘ARR[i]’ represents the array element. 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

In this approach, we will make a frequency hashmap to store the frequencies of all the array elements.
Now for every element present in the hashmap, we would check whether it forms a subset with the next (K - 1) elements or not. If so we will reduce the frequency of elements included in the subset from the hashmap and then proceed forward with the next element.
If any element is found which cannot be grouped in our subset of k consecutive elements then we will return False otherwise return True.

Algorithm:

First check whether N % K != 0 . If so, return False otherwise proceed with the below steps.
Take a hashmap ‘freq’ to store the frequencies of array elements.
Now traverse the hashmap and get the first smallest element from the map given by ‘start’.
Check whether there are ‘K’ consecutive numbers, then update the map.
- If (start + i) where 0 <= i < K is present in the map then,
  - If freq[start + i] > 0 then freq[start + i]--.
  - If freq[start + i] becomes 0, then erase that element from ‘freq’.
- Otherwise, return False if the next consecutive element is not found in the map.
Finally, return True if the map is empty.

Solve now