/* A program to find the largest multiple of 3 from an array of elements */

#include <stdio.h>

#include <stdlib.h>

  

// A queue node

typedef struct Queue {

    int front;

    int rear;

    int capacity;

    int* array;

} Queue;

  

// A utility function to create a queue with given capacity

Queue* createQueue(int capacity)

{

    Queue* queue = (Queue*)malloc(sizeof(Queue));

    queue->capacity = capacity;

    queue->front = queue->rear = -1;

    queue->array = (int*)malloc(queue->capacity * sizeof(int));

    return queue;

}

  

// A utility function to check if queue is empty

int isEmpty(Queue* queue)

{

    return queue->front == -1;

}

  

// A function to add an item to queue

void Enqueue(Queue* queue, int item)

{

    queue->array[++queue->rear] = item;

    if (isEmpty(queue))

        ++queue->front;

}

  

// A function to remove an item from queue

int Dequeue(Queue* queue)

{

    int item = queue->array[queue->front];

    if (queue->front == queue->rear)

        queue->front = queue->rear = -1;

    else

        queue->front++;

  

    return item;

}

  

// A utility function to print array contents

void printArr(int* arr, int size)

{

    int i;

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

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

}

  

/* Following two functions are needed for library function qsort().*/

int compareAsc(const void* a, const void* b)

{

    return *(int*)a > *(int*)b;

}

int compareDesc(const void* a, const void* b)

{

    return *(int*)a < *(int*)b;

}

  

// This function puts all elements of 3 queues in the auxiliary array

void populateAux(int* aux, Queue* queue0, Queue* queue1,

                 Queue* queue2, int* top)

{

    // Put all items of first queue in aux[]

    while (!isEmpty(queue0))

        aux[(*top)++] = Dequeue(queue0);

  

    // Put all items of second queue in aux[]

    while (!isEmpty(queue1))

        aux[(*top)++] = Dequeue(queue1);

  

    // Put all items of third queue in aux[]

    while (!isEmpty(queue2))

        aux[(*top)++] = Dequeue(queue2);

}

  

/* The main function that finds the largest possible multiple of 3 that can be formed by arr[] elements */

int findMaxMultupleOf3(int* arr, int size)

{

    // Step 1: sort the array in non-decreasing order

    qsort(arr, size, sizeof(int), compareAsc);

  

    // Create 3 queues to store numbers with remainder 0, 1 and 2 respectively

    Queue* queue0 = createQueue(size);

    Queue* queue1 = createQueue(size);

    Queue* queue2 = createQueue(size);

  

    // Step 2 and 3 get the sum of numbers and place them in corresponding queues

    int i, sum;

    for (i = 0, sum = 0; i < size; ++i) {

        sum += arr[i];

        if ((arr[i] % 3) == 0)

            Enqueue(queue0, arr[i]);

        else if ((arr[i] % 3) == 1)

            Enqueue(queue1, arr[i]);

        else

            Enqueue(queue2, arr[i]);

    }

  

    // Step 4.2: The sum produces remainder 1

    if ((sum % 3) == 1) {

        // either remove one item from queue1

        if (!isEmpty(queue1))

            Dequeue(queue1);

  

        // or remove two items from queue2

        else {

            if (!isEmpty(queue2))

                Dequeue(queue2);

            else

                return 0;

  

            if (!isEmpty(queue2))

                Dequeue(queue2);

            else

                return 0;

        }

    }

  

    // Step 4.3: The sum produces remainder 2

    else if ((sum % 3) == 2) {

        // either remove one item from queue2

        if (!isEmpty(queue2))

            Dequeue(queue2);

  

        // or remove two items from queue1

        else {

            if (!isEmpty(queue1))

                Dequeue(queue1);

            else

                return 0;

  

            if (!isEmpty(queue1))

                Dequeue(queue1);

            else

                return 0;

        }

    }

  

    int aux[size], top = 0;

  

    // Empty all the queues into an auxiliary array.

    populateAux(aux, queue0, queue1, queue2, &top);

  

    // sort the array in non-increasing order

    qsort(aux, top, sizeof(int), compareDesc);

  

    // print the result

    printArr(aux, top);

  

    return top;

}

  

// Driver program to test above functions

int main()

{

    int arr[] = { 8, 1, 7, 6, 0 };

    int size = sizeof(arr) / sizeof(arr[0]);

  

    if (findMaxMultupleOf3(arr, size) == 0)

        printf("Not Possible");

  

    return 0;

}