Construct a sequence from given frequencies of N consecutive integers with unit adjacent difference | 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
def generateSequence ( freq , n ) : NEW_LINE INDENT m = { } NEW_LINE total = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ i ] = freq [ i ] NEW_LINE total += freq [ i ] NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( m [ i ] ) : NEW_LINE INDENT sequence = [ ] NEW_LINE mcopy = { } NEW_LINE for j in m : NEW_LINE INDENT mcopy [ j ] = m [ j ] NEW_LINE DEDENT mcopy [ i ] -= 1 NEW_LINE sequence . append ( i ) NEW_LINE last = i NEW_LINE for j in range ( total - 1 ) : NEW_LINE INDENT if ( ( last - 1 ) in mcopy and mcopy [ last - 1 ] > 0 ) : NEW_LINE INDENT mcopy [ last - 1 ] -= 1 NEW_LINE sequence . append ( last - 1 ) NEW_LINE last -= 1 NEW_LINE DEDENT elif ( mcopy [ last + 1 ] ) : NEW_LINE INDENT mcopy [ last + 1 ] -= 1 NEW_LINE sequence . append ( last + 1 ) NEW_LINE last += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( len ( sequence ) == total ) : NEW_LINE INDENT return sequence NEW_LINE DEDENT DEDENT DEDENT return [ ] NEW_LINE DEDENT def PrintSequence ( freq , n ) : NEW_LINE INDENT sequence = generateSequence ( freq , n ) NEW_LINE if ( len ( sequence ) == 0 ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( len ( sequence ) ) : NEW_LINE INDENT print ( sequence [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT freq = [ 2 , 2 , 2 , 3 , 1 ] NEW_LINE N = 5 NEW_LINE PrintSequence ( freq , N ) NEW_LINE DEDENT