Construct a sequence from given frequencies of N consecutive integers with unit adjacent difference | C ++ program for the above approach ; Function generates the sequence ; Map to store the frequency of numbers ; Sum of all frequencies ; Try all possibilities for the starting element ; If the frequency of current element is non - zero ; vector to store the answer ; Copy of the map for every possible starting element ; Decrement the frequency ; Push the starting element to the vector ; The last element inserted is i ; Try to fill the rest of the positions if possible ; If the frequency of last - 1 is non - zero ; Decrement the frequency of last - 1 ; Insert it into the sequence ; Update last number added to sequence ; Break from the inner loop ; If the size of the sequence vector is equal to sum of total frequqncies ; Return sequence ; If no such sequence if found return empty sequence ; Function Call to print the sequence ; The required sequence ; If the size of sequence if zero it means no such sequence was found ; Otherwise print the sequence ; Driver Code ; Frequency of all elements from 0 to n - 1 ; Number of elements whose frequencies are given ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > generateSequence ( int * freq , int n ) { map < int , int > m ; int total = 0 ; for ( int i = 0 ; i < n ; i ++ ) { m [ i ] = freq [ i ] ; total += freq [ i ] ; } for ( int i = 0 ; i < n ; i ++ ) { if ( m [ i ] ) { vector < int > sequence ; auto mcopy = m ; mcopy [ i ] -- ; sequence . push_back ( i ) ; int last = i ; for ( int i = 0 ; i < total - 1 ; i ++ ) { if ( mcopy [ last - 1 ] ) { mcopy [ last - 1 ] -- ; sequence . push_back ( last - 1 ) ; last -- ; } else if ( mcopy [ last + 1 ] ) { mcopy [ last + 1 ] -- ; sequence . push_back ( last + 1 ) ; last ++ ; } else break ; } if ( sequence . size ( ) == total ) { return sequence ; } } } vector < int > empty ; return empty ; } void PrintSequence ( int freq [ ] , int n ) { vector < int > sequence = generateSequence ( freq , n ) ; if ( sequence . size ( ) == 0 ) { cout << " - 1" ; } else { for ( int i = 0 ; i < sequence . size ( ) ; i ++ ) { cout << sequence [ i ] << " ▁ " ; } } } int main ( ) { int freq [ ] = { 2 , 2 , 2 , 3 , 1 } ; int N = 5 ; PrintSequence ( freq , N ) ; return 0 ; }