Divide Array into Sets of K Consecutive Numbers in C++

Suppose we have an array of integers nums and a positive integer k, we have to find whether it's possible to divide this array into sets of k consecutive numbers. So we have to return True if its possible otherwise return False. So if the input is like [1,2,3,3,4,4,5,6] and k = 4, then output will be true. This is because, we can divide the array such that [1,2,3,4] and [3,4,5,6]

To solve this, we will follow these steps −

• Make one map m, set n := size of nums array
• for each element e in nums
  • increase m[e] by 1
• cnt := 0
• sort nums array
• for i in range 0 to n
  • x := nums[i]
  • if m[x – 1] = 0 and m[x] > 0
    • l := k
    • while k > 0
      • if m[x] > 0, then decrease the value of m[k] by 1, otherwise return false
      • increase x and cnt by 1, and decrease k by 1
    • k := l
• return true when cnt = n, otherwise false

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPossibleDivide(vector<int>& nums, int k) {
      map <int, int> m;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         m[nums[i]]++;
      }
      int cnt = 0;
      sort(nums.begin(), nums.end());
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(m[x - 1] == 0 && m[x] > 0){
            int l = k;
            while(k>0){
               if(m[x] > 0){
                  m[x]--;
            } else return false;
               x++;
               k--;
               cnt++;
            }
            k = l;
         }
      }
     return cnt == n;
   }
};
main(){
   vector<int> v = {1,2,3,3,4,4,5,6};
   Solution ob;
   cout << (ob.isPossibleDivide(v, 4));
}

Input

[1,2,3,3,4,4,5,6]
4

Output

1