Find the largest multiple of 3 from array of digits | Set 2 ( In O ( n ) time and O ( 1 ) space ) | C ++ program to find the largest number that can be mode from elements of the array and is divisible by 3 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_SIZE  10 NEW_LINE void sortArrayUsingCounts ( int arr [ ] , int n ) { int count [ MAX_SIZE ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) count [ arr [ i ] ] ++ ; int index = 0 ; for ( int i = 0 ; i < MAX_SIZE ; i ++ ) while ( count [ i ] > 0 ) arr [ index ++ ] = i , count [ i ] -- ; } bool removeAndPrintResult ( int arr [ ] , int n , int ind1 , int ind2 = -1 ) { for ( int i = n - 1 ; i >= 0 ; i -- ) if ( i != ind1 && i != ind2 ) cout << arr [ i ] ; } bool largest3Multiple ( int arr [ ] , int n ) { int sum = accumulate ( arr , arr + n , 0 ) ; if ( sum % 3 == 0 ) return true ; sortArrayUsingCounts ( arr , n ) ; int remainder = sum % 3 ; if ( remainder == 1 ) { int rem_2 [ 2 ] ; rem_2 [ 0 ] = -1 , rem_2 [ 1 ] = -1 ; for ( int 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 ) { int rem_1 [ 2 ] ; rem_1 [ 0 ] = -1 , rem_1 [ 1 ] = -1 ; for ( int 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 ; } } cout << " Not ▁ possible " ; return false ; } int main ( ) { int arr [ ] = { 4 , 4 , 1 , 1 , 1 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; largest3Multiple ( arr , n ) ; return 0 ; }