Construct a sequence from given frequencies of N consecutive integers with unit adjacent difference | Java 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
import java . util . * ; class GFG { static Vector < Integer > generateSequence ( int [ ] freq , int n ) { HashMap < Integer , Integer > m = new HashMap < Integer , Integer > ( ) ; int total = 0 ; for ( int i = 0 ; i < n ; i ++ ) { m . put ( i , freq [ i ] ) ; total += freq [ i ] ; } for ( int i = 0 ; i < n ; i ++ ) { if ( m . containsKey ( i ) ) { Vector < Integer > sequence = new Vector < Integer > ( ) ; @ SuppressWarnings ( " unchecked " ) HashMap < Integer , Integer > mcopy = ( HashMap < Integer , Integer > ) m . clone ( ) ; if ( mcopy . containsKey ( i ) && mcopy . get ( i ) > 0 ) mcopy . put ( i , mcopy . get ( i ) - 1 ) ; sequence . add ( i ) ; int last = i ; for ( int i1 = 0 ; i1 < total - 1 ; i1 ++ ) { if ( mcopy . containsKey ( last - 1 ) && mcopy . get ( last - 1 ) > 0 ) { mcopy . put ( last - 1 , mcopy . get ( last - 1 ) - 1 ) ; sequence . add ( last - 1 ) ; last -- ; } else if ( mcopy . containsKey ( last + 1 ) ) { mcopy . put ( last + 1 , mcopy . get ( last + 1 ) - 1 ) ; sequence . add ( last + 1 ) ; last ++ ; } else break ; } if ( sequence . size ( ) == total ) { return sequence ; } } } Vector < Integer > empty = new Vector < Integer > ( ) ; return empty ; } static void PrintSequence ( int freq [ ] , int n ) { Vector < Integer > sequence = generateSequence ( freq , n ) ; if ( sequence . size ( ) == 0 ) { System . out . print ( " - 1" ) ; } else { for ( int i = 0 ; i < sequence . size ( ) ; i ++ ) { System . out . print ( sequence . get ( i ) + " ▁ " ) ; } } } public static void main ( String [ ] args ) { int freq [ ] = { 2 , 2 , 2 , 3 , 1 } ; int N = 5 ; PrintSequence ( freq , N ) ; } }