Find the largest multiple of 3 from array of digits in O(n) time complexity

user_7219095 0
Viewed 1203

Given an array of digits (0 to 9). Find the largest number that can be made from some or all digits of array and is divisible by 3. The same element may appear multiple times in the array, but each element in the array may only be used once. Examples: Input : arr[] = {5, 4, 3, 1, 1} Output : 4311

Algorithm

  1. Get array size and array input and calculate sum while getting input.
  2. Sort the array in ascending order
  3. Take three queues, Iterate array and divide digit by 3 and put in respective queues based on remainder,
    Queue0 to hold digit % 3 == 0
    Queue1 to hold digit % 3 == 1
    Queue2 to hold digit % 3 == 2
  4. Calculate remainder = sum % 3,
    if remainder is equal to 1, Dequeue one element from Queue1 or two dequeue from Queue2
    else if remainder is equal to 2 Dequeue one element from Queue2 or two dequeue from Queue1
  5. Merge Queue0, Queue1 and Queue2 into one queue
  6. Sort merge queue in descending order
  7. Print merged queue.

Code

#include<stdio.h> 
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    int a[n],q1[n],q2[n],q3[n];
    int c1=0,c2=0,c3=0;
    for(int i=0;i<n;i++) {
    scanf("%d",&a[i]);
    sum+=a[i]; }
    for(int i=0;i<n;i++){
        if(a[i]%3==0) {
            q1[c1]=a[i]; c1++; }
        else if(a[i]%3==1) {
            q2[c2]=a[i]; c2++; }
        else {
            q3[c3]=a[i]; c3++; }
    }
    if(sum%3==1&&c1!=0)
    c1--;
    else {
        if(c2>1)
            c2-2;
        else
            printf("Not Possible");
    }
    if(sum%3==2&&c2!=0)
    c2--;
    else {
        if(q1>1)
            c1-2;
        else
            printf("Not Possible");
    }
    int k=0,b[n];
    for(int i=0;i<c1;i++) {
        b[k]=q1[i]; k++; }
    for(int i=0;i<c2;i++) {
        b[k]=q2[i]; k++; }
    for(int i=0;i<c3;i++) {
        b[k]=q3[i]; k++; }
    }

I am new to coding and couldn't figure out sorting and merging queue in O(n). Need help with step 2 and 5.

c
2 Answers

To sort in O(n), you'll want to use Radix sort.

// Let's start with the array that your code generates in step 5
int b[4] = {1, 1, 4, 3}

// Count the number of times each value is seen.
int buckets[10] = {};
for (int i=0; i<4; i++)
  buckets[b[i]]++;

// Update the b array with the sorted data.
int *b_iterator = &b[0];
for (int i=0; i<10; i++)
  for (int count=0; count<buckets[i]; count++)
    *b_iterator++ = i;

// b is now sorted. {1, 1, 3, 4}.
user_474530

1.Sort the array in increasing order(Counting Sort).
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.

#include<stdio.h> 
int main()
{
    int n,max,f=0,c=0;
    scanf("%d",&n);
    int a[n],ct[10]={0},b[10],sum=0;
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];}
    max=a[0];
    for(int i=0;i<n;i++)
        if(max<a[i])
            max=a[i];
    for(int i=0;i<n;i++)
        ct[a[i]]+=1;
    for(int i=1;i<=max;i++)
        ct[i]+=ct[i-1];
    for(int i=n-1;i>=0;i--)
        b[--ct[a[i]]]=a[i];
    if(sum%3==0)
        goto print;
    else if(sum%3==1) {
        for(int i=n-1;i>=0;i--)
            if(b[i]%3==1) {
                b[i]=-1; f=1;
                goto print;
            }
    }
    else {
        for(int i=n-1;i>=0;i--)
            if(b[i]%3==2) {
                b[i]=-1; f=1;
                goto print;
            }
    }
    if(f==0&&sum%3==1) {
        for(int i=n-1;i>=0&&c<2;i--)
            if(b[i]%3==2) {
                b[i]=-1;
                c++;
            }
    }
    if(f==0&&sum%3==2) {
        for(int i=n-1;i>=0&&c<2;i--)
            if(b[i]%3==1) {
                b[i]=-1;
                c++;
            }
    }
    print:
    for(int i=n-1;i>=0;i--)
        if(b[i]!=-1)
            printf("%d",b[i]);
    return 0;
}
user_72190950
Related