Given an array of non-negative integers. Find the largest multiple of 3 that can be formed from array elements. For example, if the input array is {8, 1, 9}, the output should be “9 8 1″, and if the input array is {8, 1, 7, 6, 0}, output should be “8 7 6 0″.

LargestMultipleOfThree.java

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LargeMultipleThree {
	
	//method to loas the list when queues are dequeued
	public static void loadAux(List<Integer> aux,Queue<?> q,Queue<?> q1, Queue<?> q2){
		
		while(!q.isEmpty()){
			aux.add((Integer) q.remove());
			
		}
		while(!q1.isEmpty()){
			aux.add((Integer) q1.remove());
			
		}
		while(!q2.isEmpty()){
			aux.add((Integer) q2.remove());
			
		}
		
	}
	
	public static int solution(int[] arr){
		
		//create 3 queues
		Queue<Integer> q = new LinkedList<Integer>();
		Queue<Integer> q1 = new LinkedList<Integer>();
		Queue<Integer> q2 = new LinkedList<Integer>();
		
		int sum = 0;
		//scan through array getting the sum 
		
		for (int i = 0; i<arr.length;i++){
			
			sum = sum + arr[i];
			
			//checks if each digit has a remainder of 0 modulus 3
			//then adds it to q
			if(arr[i]%3 == 0){
				q.add(arr[i]);
			}
			//checks if each digit has a remainder of 1 modulus 3
			else if(arr[i]%3 ==1){
				q1.add(arr[i]);
			}
			else{
				q2.add(arr[i]);
			}
		}
		
		
		if(sum%3 == 1){
			if(!q1.isEmpty()){ ////if sum mod 3 is 1 remove first element in q1
				q1.remove();
			}
			else{// remove 2 elements from q2, otherewise number is not a multiple of 3
				if(!q2.isEmpty()){
					q2.remove();
				}
				else{
					return 0;
				}
				if(!q2.isEmpty()){
					q2.remove();
				}
				else{
					return 0;
				}
			}
		}
		
		if(sum%3 == 2){
			if(!q2.isEmpty()){
				q2.remove();
			}
			else{
				if(!q1.isEmpty()){
					q1.remove();
				}
				else{
					return 0;
				}
				if(!q1.isEmpty()){
					q1.remove();
				}
				else{
					return 0;
				}
			}
		}
		
		List<Integer> aux = new ArrayList<Integer>();
		loadAux(aux, q, q1, q2);
		
		//sorts the list
		Collections.sort(aux);
		//reverses the list
		Collections.reverse(aux);
		
		for(int i=0;i<aux.size();i++){
			System.out.println(aux.toString());
		}
		
		return 1;
	}
	
	public static void main(String[]args){
		
		int[] test = {8,1,7,6,0};
		solution(test);
	}

}

this problem almost ok but i want to see some more improvements
Fill 3 queusrs
q0 elments which give 0 when take modulo with 3
q1 elements which give 1
q2 elements which give 2

now sort all these queue in decreasing order

if sum is 0 then just sort main queue

if sum give 1 as modulo then if q1 is not empty remove 1 element fron tail side
else if sum give 1 as module and q1 is empty remove two least element from q2
note:- if q2 not have 2 elements then we cannot make a no multiple of 3 handle this also

same way if remoinder is 2

remove 1 least element from q2 if q2 is empty then remove 2 least element from q1 and if q1 not have 2 element then we cannot make a no multiple of 3.....