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]
