Find the largest multiple of 3 from array of digits | Set 2 ( In O ( n ) time and O ( 1 ) space ) | Number of digits ; function to sort array of digits using counts ; Store count of all elements ; Store ; Remove elements from arr [ ] at indexes ind1 and ind2 ; Returns largest multiple of 3 that can be formed using arr [ ] elements . ; Sum of all array element ; Sum is divisible by 3 , no need to delete an element ; Sort array element in increasing order ; Find reminder ; If remainder is '1' , we have to delete either one element of remainder '1' or two elements of remainder '2' ; Traverse array elements ; Store first element of remainder '1' ; If this is first occurrence of remainder 2 ; If second occurrence ; If remainder is '2' , we have to delete either one element of remainder '2' or two elements of remainder '1' ; traverse array elements ; store first element of remainder '2' ; If this is first occurrence of remainder 1 ; If second occurrence ; Driver code
const MAX_SIZE = 10 ; function sortArrayUsingCounts ( arr , n ) { let count = new Uint8Array ( MAX_SIZE ) ; for ( let i = 0 ; i < n ; i ++ ) count [ arr [ i ] ] ++ ; let index = 0 ; for ( let i = 0 ; i < MAX_SIZE ; i ++ ) while ( count [ i ] > 0 ) arr [ index ++ ] = i , count [ i ] -- ; } function removeAndPrintResult ( arr , n , ind1 , ind2 = - 1 ) { for ( let i = n - 1 ; i >= 0 ; i -- ) if ( i != ind1 && i != ind2 ) document . write ( arr [ i ] ) ; } function largest3Multiple ( arr , n ) { let sum = arr . reduce ( ( a , b ) => a + b , 0 ) ; if ( sum % 3 == 0 ) return true ; sortArrayUsingCounts ( arr , n ) ; let remainder = sum % 3 ; if ( remainder == 1 ) { let rem_2 = new Array ( 2 ) ; rem_2 [ 0 ] = - 1 , rem_2 [ 1 ] = - 1 ; for ( let i = 0 ; i < n ; i ++ ) { if ( arr [ i ] % 3 == 1 ) { removeAndPrintResult ( arr , n , i ) ; return true ; } if ( arr [ i ] % 3 == 2 ) { if ( rem_2 [ 0 ] == - 1 ) rem_2 [ 0 ] = i ; else if ( rem_2 [ 1 ] == - 1 ) rem_2 [ 1 ] = i ; } } if ( rem_2 [ 0 ] != - 1 && rem_2 [ 1 ] != - 1 ) { removeAndPrintResult ( arr , n , rem_2 [ 0 ] , rem_2 [ 1 ] ) ; return true ; } } else if ( remainder == 2 ) { let rem_1 = new Array ( 2 ) ; rem_1 [ 0 ] = - 1 , rem_1 [ 1 ] = - 1 ; for ( let i = 0 ; i < n ; i ++ ) { if ( arr [ i ] % 3 == 2 ) { removeAndPrintResult ( arr , n , i ) ; return true ; } if ( arr [ i ] % 3 == 1 ) { if ( rem_1 [ 0 ] == - 1 ) rem_1 [ 0 ] = i ; else if ( rem_1 [ 1 ] == - 1 ) rem_1 [ 1 ] = i ; } } if ( rem_1 [ 0 ] != - 1 && rem_1 [ 1 ] != - 1 ) { removeAndPrintResult ( arr , n , rem_1 [ 0 ] , rem_1 [ 1 ] ) ; return true ; } } document . write ( " " ) ; return false ; } let arr = [ 4 , 4 , 1 , 1 , 1 , 3 ] ; let n = arr . length ; largest3Multiple ( arr , n ) ;