Check if given Array can be divided into subsequences of K increasing consecutive integers | C ++ program for the above approach ; Function to check if the array can be divided into subsequences of K consecutive integers in increasing order ; If N is not divisible by K or K > N , no possible set of required subsequences exist ; Stores the indices of each element in a set ; Stores the index of each number ; Stores if the integer at current index is already included in a subsequence ; Stores the count of total visited elements ; If current integer is already in a subsequence ; Stores the value of last element of the current subsequence ; Stores the index of last element of the current subsequence ; Mark Visited ; Increment the visited count ; Find the next K - 1 elements of the subsequence starting from index i ; No valid index found ; Find index of j such that it is greater than last_index ; if no such index found , return false ; Update last_index ; Mark current index as visited ; Increment total_visited by 1 ; Remove the index from set because it has been already used ; Return the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( vector < int > nums , int K ) { int N = nums . size ( ) ; if ( N % K != 0 K > N ) { return false ; } map < int , set < int > > idx ; for ( int i = 0 ; i < nums . size ( ) ; i ++ ) { idx [ nums [ i ] ] . insert ( i ) ; } int visited [ N ] = { 0 } ; int total_visited = 0 ; for ( int i = 0 ; i < nums . size ( ) ; i ++ ) { if ( visited [ i ] ) { continue ; } int num = nums [ i ] ; int last_index = i ; visited [ i ] = 1 ; total_visited ++ ; for ( int j = num + 1 ; j < num + K ; j ++ ) { if ( idx [ j ] . size ( ) == 0 ) { return false ; } auto it = idx [ j ] . upper_bound ( last_index ) ; if ( it == idx [ j ] . end ( ) * it <= last_index ) { return false ; } last_index = * it ; visited [ last_index ] = 1 ; total_visited ++ ; idx [ j ] . erase ( it ) ; } } return total_visited == N ; } int main ( ) { vector < int > arr = { 4 , 3 , 1 , 2 } ; int K = 2 ; cout << ( isPossible ( arr , K ) ? " Yes " : " No " ) ; return 0 ; }