Given an array of digits,the task is to find the largest multiple of 3 that can be formed from array elements.

**Example-**

Input array is {4,8,0}.Then,the largest number formed using these digits and divisible by 3 is 840.

**Properties of multiples of 3-**

**1.**Sum of the digits of the multiple is divisible by 3.

*Example-*

840 is divisible by 3 and (8+4+0=12) is also divisible by 3.

**2.**We get the same remainder when we divide the number and sum of digits of the number by 3.

*Example-*

841 when divided by 3 gives remainder 1.

(8+4+1=13) when divided by 3 also gives remainder 1.

**Naive Algorithm-**

Generate all the combinations of the given digits and maximum of the numbers which is divisible by 3 is the result.

But,it will have a time complexity of O(2^n).

**Efficient Algorithm-**

**1.**Sort the array in increasing order.

**2.**Queue q0 stores the elements which on dividing by 3 gives remainder 0.

**3.**Queue q1 stores the elements which on dividing by 3 gives remainder 1.

**4.**Queue q2 stores the elements which on dividing by 3 gives remainder 2.

**5.**Find the sum of all the given digits.Let it be ‘s’.

**6.**If s is divisible by 3,goto step 9.

**7.**If s when divided by 3 gives remainder 1:

Remove one item from q1.

If q1 is empty,remove two items from q2.

If q2 contains less than two elements,number is not possible.

**8.**If s when divided by 3 gives remainder 2:

Remove one item from q2.

If q2 is empty,remove two items from q1.

If q1 contains less than two elements,number is not possible.

**9.**Empty all queues into an temporary array and sort it in decreasing order.

**Code-**

[cpp]

//a[] is the input array

//s is the sum of the digits

//n is the number of digits in the given array

#include<stdio.h>

#include<algorithm>

#include<queue>

int main()

{

using namespace std;

int i,n,s,a[1000],p[1000],w,z;

queue<int> q0;

queue<int> q1;

queue<int> q2;

scanf("%d",&n);s=0;

//taking the input

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

s=s+a[i];

}

sort(a,a+n);

for(i=0;i<n;i++)

{

if(a[i]%3==0) q0.push(a[i]);

else if(a[i]%3==1) q1.push(a[i]);

else q2.push(a[i]);

}

if(s%3==1)

{

// either remove one item from queue1

if ( !q1.empty() )

q1.pop();

// or remove two items from queue2

else

{

if ( !q2.empty() )

q2.pop();

else printf("No number can be formed\n");

if ( !q2.empty() )

q2.pop();

else printf("No number can be formed\n");

}

}

else if ((s% 3) == 2)

{

// either remove one item from queue2

if ( !q2.empty() )

q2.pop();

// or remove two items from queue1

else

{

if ( !q1.empty() )

q1.pop();

else

printf("No number can be formed\n");

if ( !q1.empty() )

q1.pop();

else

printf("No number can be formed\n");

}

}

//emptying all the queues

w=0;

while(!q0.empty())

{

z=q0.front();

p[w++]=z;

q0.pop();

}

while(!q1.empty())

{

z=q1.front();

p[w++]=z;

q1.pop();

}

while(!q2.empty())

{

z=q2.front();

p[w++]=z;

q2.pop();

}

sort(p,p+w);

//printing in descending order

for(i=w-1;i>=0;i–)

printf("%d",p[i]);

return 0;

}

[/cpp]