Permutation of Array such that sum of adjacent elements are not divisible by 3 | Python3 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
hell = 1000000007 NEW_LINE N = 100005 NEW_LINE c_0 = 0 NEW_LINE c_1 = 0 NEW_LINE c_2 = 0 NEW_LINE def count_k ( arr , ones , twos , zeros ) : NEW_LINE INDENT global c_0 , c_1 , c_2 NEW_LINE for i in range ( len ( arr ) ) : NEW_LINE INDENT if ( arr [ i ] % 3 == 0 ) : NEW_LINE INDENT c_0 += 1 NEW_LINE zeros . append ( arr [ i ] ) NEW_LINE DEDENT elif ( arr [ i ] % 3 == 1 ) : NEW_LINE INDENT c_1 += 1 NEW_LINE ones . append ( arr [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT c_2 += 1 NEW_LINE twos . append ( arr [ i ] ) NEW_LINE DEDENT DEDENT DEDENT def printArrangement ( arr , ones , twos , zeros ) : NEW_LINE INDENT global c_0 , c_1 , c_2 NEW_LINE if ( ( c_0 == 0 and c_1 != 0 and c_2 != 0 ) or c_0 > c_1 + c_2 + 1 ) : NEW_LINE INDENT print ( " - 1" , end = " " ) NEW_LINE return NEW_LINE DEDENT if ( c_0 == 0 ) : NEW_LINE INDENT for i in range ( len ( arr ) ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT return NEW_LINE DEDENT ans = [ - 1 ] * N NEW_LINE i , j = 1 , 0 NEW_LINE while ( j < c_1 ) : NEW_LINE INDENT ans [ i ] = ones [ - 1 ] NEW_LINE ones . pop ( ) NEW_LINE i += 2 NEW_LINE j += 1 NEW_LINE DEDENT ans [ i - 1 ] = zeros [ - 1 ] NEW_LINE zeros . pop ( ) NEW_LINE c_0 -= 1 NEW_LINE j = 0 NEW_LINE while ( j < c_2 ) : NEW_LINE INDENT ans [ i ] = twos [ - 1 ] NEW_LINE twos . pop ( ) NEW_LINE j += 1 NEW_LINE i += 2 NEW_LINE DEDENT k = 0 NEW_LINE while c_0 > 0 : NEW_LINE INDENT if ( ans [ k ] == - 1 ) : NEW_LINE INDENT ans [ k ] = zeros [ - 1 ] NEW_LINE c_0 -= 1 NEW_LINE DEDENT k += 2 NEW_LINE DEDENT for i1 in range ( N ) : NEW_LINE INDENT if ( ans [ i1 ] != - 1 ) : NEW_LINE INDENT print ( ans [ i1 ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT return NEW_LINE DEDENT def solve ( n , arr ) : NEW_LINE INDENT ones = [ ] NEW_LINE zeros = [ ] NEW_LINE twos = [ ] NEW_LINE count_k ( arr , ones , twos , zeros ) NEW_LINE printArrangement ( arr , ones , twos , zeros ) NEW_LINE DEDENT n = 5 NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE solve ( n , arr ) NEW_LINE