Permutation of Array such that sum of adjacent elements are not divisible by 3 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define hell  1000000007 NEW_LINE #define N  100005 NEW_LINE void count_k ( vector < int > & arr , int & c_0 , int & c_1 , int & c_2 , stack < int > & ones , stack < int > & twos , stack < int > & zeros ) { for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { if ( arr [ i ] % 3 == 0 ) { c_0 ++ ; zeros . push ( arr [ i ] ) ; } else if ( arr [ i ] % 3 == 1 ) { c_1 ++ ; ones . push ( arr [ i ] ) ; } else { c_2 ++ ; twos . push ( arr [ i ] ) ; } } return ; } void printArrangement ( vector < int > & arr , int & c_0 , int & c_1 , int & c_2 , stack < int > & ones , stack < int > & twos , stack < int > & zeros ) { if ( ( c_0 == 0 && c_1 != 0 && c_2 != 0 ) or c_0 > c_1 + c_2 + 1 ) { cout << " - 1" ; return ; } if ( c_0 == 0 ) { for ( int i = 0 ; i < arr . size ( ) ; i ++ ) { cout << arr [ i ] << " ▁ " ; } return ; } int i , j , ans [ N ] ; memset ( ans , -1 , sizeof ( ans ) ) ; for ( i = 1 , j = 0 ; j < c_1 ; i += 2 , j ++ ) { ans [ i ] = ones . top ( ) ; ones . pop ( ) ; } ans [ i - 1 ] = zeros . top ( ) ; zeros . pop ( ) ; c_0 -- ; for ( j = 0 ; j < c_2 ; j ++ , i += 2 ) { ans [ i ] = twos . top ( ) ; twos . pop ( ) ; } for ( int k = 0 ; c_0 > 0 ; k += 2 ) { if ( ans [ k ] == -1 ) { ans [ k ] = zeros . top ( ) ; c_0 -- ; } } for ( int i = 0 ; i < N ; i ++ ) { if ( ans [ i ] != -1 ) cout << ans [ i ] << " ▁ " ; } return ; } void solve ( int n , vector < int > & arr ) { stack < int > ones , zeros , twos ; int c_0 = 0 , c_1 = 0 , c_2 = 0 ; count_k ( arr , c_0 , c_1 , c_2 , ones , twos , zeros ) ; printArrangement ( arr , c_0 , c_1 , c_2 , ones , twos , zeros ) ; } signed main ( ) { int n = 5 ; vector < int > arr { 1 , 2 , 3 , 4 , 5 } ; solve ( n , arr ) ; return 0 ; }