Answered! Using queue, write an algorithm to find the largest multiple of 3 in the following array:…

#include <stdio.h>

typedef struct Queue
{
int front;
int rear;
int cap;
int* arr;
} Queue;

// A utility function to create a queue with given cap
Queue* makeQueue( int cap )
{
Queue* q = (Queue *) malloc (sizeof(Queue));
q->cap = cap;
q->front = q->rear = -1;
q->arr = (int *) malloc (q->cap * sizeof(int));
return q;
}

int isEmpty (Queue* q)
{
return q->front == -1;
}

void Enqueue (Queue* q, int item)
{
q->arr[ ++q->rear ] = item;
if ( isEmpty(q) )
++q->front;
}

int Dequeue (Queue* q)
{
int item = q->arr[ q->front ];
if( q->front == q->rear )
q->front = q->rear = -1;
else
q->front++;

return item;
}

void printArr (int* arr, int size)
{
int i;
for (i = 0; i< size; ++i)
printf (“%d “, arr[i]);
}

// for sorting
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 populateArr (int* aux, Queue* q0, Queue* q1,
Queue* q2, int* top )
{
// Put all items of first queue in aux[]
while ( !isEmpty(q0) )
aux[ (*top)++ ] = Dequeue( q0 );

// Put all items of second queue in aux[]
while ( !isEmpty(q1) )
aux[ (*top)++ ] = Dequeue( q1 );

// Put all items of third queue in aux[]
while ( !isEmpty(q2) )
aux[ (*top)++ ] = Dequeue( q2 );
}

int findNum( 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* q0 = makeQueue( size );
Queue* q1 = makeQueue( size );
Queue* q2 = makeQueue( 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( q0, arr[i] );
else if ( (arr[i] % 3) == 1 )
Enqueue( q1, arr[i] );
else
Enqueue( q2, arr[i] );
}

if ( (sum % 3) == 1 )
{
// either remove one item from q1
if ( !isEmpty( q1 ) )
Dequeue( q1 );

// or remove two items from q2
else
{
if ( !isEmpty( q2 ) )
Dequeue( q2 );
else
return 0;

if ( !isEmpty( q2 ) )
Dequeue( q2 );
else
return 0;
}
}

else if ((sum % 3) == 2)
{
// either remove one item from q2
if ( !isEmpty( q2 ) )
Dequeue( q2 );

// or remove two items from q1
else
{
if ( !isEmpty( q1 ) )
Dequeue( q1 );
else
return 0;

if ( !isEmpty( q1 ) )
Dequeue( q1 );
else
return 0;
}
}

int aux[size], top = 0;

// Empty all the queues into an auxiliary arr.
populateArr (aux, q0, q1, q2, &top);

// sort the arr
qsort (aux, top, sizeof( int ), compareDesc);

printArr (aux, top);

return top;
}

// Main
int main()
{
int arr[] = {8, 7, 6, 4,3,9,5,4};
int size = sizeof(arr)/sizeof(arr[0]);

if (findNum( arr, size ) == 0)
printf( “Not Possible” );

return 0;
}