Permutation of Array such that sum of adjacent elements are not divisible by 3 | Java implementation to find the permutation of the array such that sum of adjacent elements is not divisible by 3 ; Function to segregate numbers based on their remainder when divided by three ; Loop to iterate over the elements of the given array ; Condition to check the remainder of the number ; Function to find the permutation of the array such that sum of adjacent elements is not divisible by 3 ; Condition to check when it 's impossible to arrange ; Condition to check when there are no zeros , and only ones or only twos ; Array to store the permutation ; Place the ones on alternate places in the answer array , leaving spaces for zeros remainder elements in the array ; Adding a zero to connect it with a two ; Place the twos on alternate places in the answer array , leaving spaces for zeros ; Fill the zeros finally , between the ones and the twos ; Print the arrangement of the array ; Function to solve the problem ; As there can be only 3 remainders ; Function Call ; Driver Code
import java . util . * ; class GFG { static final int hell = 1000000007 ; static final int N = 100005 ; static int c_0 , c_1 , c_2 ; static void count_k ( int [ ] arr , Stack < Integer > ones , Stack < Integer > twos , Stack < Integer > zeros ) { for ( int i = 0 ; i < arr . length ; i ++ ) { if ( arr [ i ] % 3 == 0 ) { c_0 ++ ; zeros . add ( arr [ i ] ) ; } else if ( arr [ i ] % 3 == 1 ) { c_1 ++ ; ones . add ( arr [ i ] ) ; } else { c_2 ++ ; twos . add ( arr [ i ] ) ; } } return ; } static void printArrangement ( int [ ] arr , Stack < Integer > ones , Stack < Integer > twos , Stack < Integer > zeros ) { if ( ( c_0 == 0 && c_1 != 0 && c_2 != 0 ) c_0 > c_1 + c_2 + 1 ) { System . out . print ( " - 1" ) ; return ; } if ( c_0 == 0 ) { for ( int i = 0 ; i < arr . length ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } return ; } int i , j ; int [ ] ans = new int [ N ] ; Arrays . fill ( ans , - 1 ) ; for ( i = 1 , j = 0 ; j < c_1 ; i += 2 , j ++ ) { ans [ i ] = ones . peek ( ) ; ones . pop ( ) ; } ans [ i - 1 ] = zeros . peek ( ) ; zeros . pop ( ) ; c_0 -- ; for ( j = 0 ; j < c_2 ; j ++ , i += 2 ) { ans [ i ] = twos . peek ( ) ; twos . pop ( ) ; } for ( int k = 0 ; c_0 > 0 ; k += 2 ) { if ( ans [ k ] == - 1 ) { ans [ k ] = zeros . peek ( ) ; c_0 -- ; } } for ( int i1 = 0 ; i1 < N ; i1 ++ ) { if ( ans [ i1 ] != - 1 ) System . out . print ( ans [ i1 ] + " ▁ " ) ; } return ; } static void solve ( int n , int [ ] arr ) { Stack < Integer > ones = new Stack < Integer > ( ) ; Stack < Integer > zeros = new Stack < Integer > ( ) ; Stack < Integer > twos = new Stack < Integer > ( ) ; c_0 = 0 ; c_1 = 0 ; c_2 = 0 ; count_k ( arr , ones , twos , zeros ) ; printArrangement ( arr , ones , twos , zeros ) ; } public static void main ( String [ ] args ) { int n = 5 ; int [ ] arr = { 1 , 2 , 3 , 4 , 5 } ; solve ( n , arr ) ; } }