Find max-number div by three to be formed by array elements

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".

Looking for code-review, best-practices and optimizations.

public final class DivThree {

    private DivThree() {}
    
    public static int divThree(int[] a) {
        final Queue queue0 = new LinkedList(); // if num % 3 == 0, store num in queue0.
        final Queue queue1 = new LinkedList(); // if num % 3 == 1, store num in queue1.
        final Queue queue2 = new LinkedList(); // if num % 3 == 2, store num in queue2.
        
        Arrays.sort(a);

        int sum = 0;
        for (int i = 0; i  list = new ArrayList();
        list.addAll(queue0);
        list.addAll(queue1);
        list.addAll(queue2);
   
        Collections.sort(list);
        
        int result = 0;
        int pow = 1;
        for (int i = 0; i < list.size(); i++) {
            result = result  + pow * list.get(i);
            pow = pow * 10;
        }
        
        return result;
    }
}

public class DivThreeTest {
    
    @Test
    public void test1() {
        int[] a1 = {1, 2, 3, 4};
        assertEquals(432, DivThree.divThree(a1));
    }

    
    @Test
    public void test2() {
        int a2[] = {8, 1, 7, 6, 0};
        assertEquals(8760, DivThree.divThree(a2));
    }
    
}

For example, if the input array is {8, 1, 9}, the output should be “9 8 1″

So, let's say that the input array is { 4, 8, 15, 16, 23, 42 }, what should the output be then? At first I expected it to be "4 8 15 16 23 42", but then @Marc-Andre made me realize that in fact, that's not the case. I misunderstood the question at first.

Although not explicitly written, all the numbers in the array are required to be less than 10. I strongly suggest you add a check in your loop: (which btw can be written as for-each instead, which also applies to your last loop for looping through the list)

for (int i : a) {
    sum = sum  + i;

    if (i >= 10) {
        throw new IllegalArgumentException("All numbers must be less than 10.");
    }

    int remainder = a % 3;
    ...
}

I have to say though that the example you give is a bit weird, as your example output is a string separated by space. The question though is about what number can be formed, which don't speak anything about string at all.

In addition to this, you also suffer from a case of severe code-duplication. This can be treated easily with the medicine of extracting method. This extracted method also deserves a little simplification as I really don't like that you're doing isEmpty-remove-isEmpty-remove, why not just check if size > 2 in the first place? (Alright, size can be a costly operation compared to isEmpty for some queue implementations, but LinkedList is not one of those - at least not anymore).

private static boolean removeOneOrTwo(Queue removeOneFrom, Queue removeTwoFrom) {
    if (!removeOneFrom.isEmpty()) {
        removeOneFrom.remove();
    } else if (removeTwoFrom.size() < 2) {
        return false;
    } else {
        removeTwoFrom.remove();
        removeTwoFrom.remove();
    }
    return true;
}

Note that here I actually use Queue, more or less just for the fun of it but mostly for the reason that for this method, it doesn't need to know what kind of Queue we're dealing with. It only needs to be able to know the size of it and remove items.

By doing this simple method extraction, we've reduced your original method a bit:

if (sum % 3 == 1) {
    if (!removeOneOrTwo(queue1, queue2)) {
        return -1;
    }
} else if (sum % 3 == 2) {
    if (!removeOneOrTwo(queue2, queue1)) {
        return -1;
    }
}

Although now that I'm dealing with that code anyway, I have to add: return -1; smells. -1 is a special return value for "no possible combination found". In this case I would find 0 a better choice of return value for that, as that would correspond to an empty array (and is a multiple of 3). Either that, or throw an exception. In this case, I would find returning zero perfectly reasonable.

StackExchange Code Review Q#55503, answer score: 6