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

Question

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<Integer> queue0 = new LinkedList<Integer>(); // if num % 3 == 0, store num in queue0.
        final Queue<Integer> queue1 = new LinkedList<Integer>(); // if num % 3 == 1, store num in queue1.
        final Queue<Integer> queue2 = new LinkedList<Integer>(); // if num % 3 == 2, store num in queue2.
        
        Arrays.sort(a);

        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum = sum  + a[i];
            
            int remainder = a[i] % 3;
            
            if (remainder == 0) {
                queue0.add(a[i]);
            } else  if (remainder == 1) {
                queue1.add(a[i]);
            } else {
                queue2.add(a[i]);
            }
        } 
        
        if (sum % 3 == 1) {
            if (!queue1.isEmpty()) {
                queue1.remove();
            } else {
                if (!queue2.isEmpty()) {
                    queue2.remove();
                } else {
                    return -1;
                }
                if (!queue2.isEmpty()) {
                    queue2.remove();
                } else {
                    return -1;
                }
            }
        } else if (sum % 3 == 2) {
            if (!queue2.isEmpty()) {
                queue2.remove();
            } else {
                if (!queue1.isEmpty()) {
                    queue1.remove();
                } else {
                    return -1;
                }
                if (!queue1.isEmpty()) {
                    queue1.remove();
                } else {
                    return -1;
                }
            }
        }
    
        final List<Integer> list = new ArrayList<Integer>();
        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));
    }
    
}

Answer 1

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.

Answer 2

There is a bug in your algorithm. Writing only two tests for your algorithm is not enough. Try this test case :

@Test
public void testWithAnArraySize10() {
    int bigArray[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    assertEquals(9876543210L, DivThree.divThree(bigArray));
}

So when your array have a size of more than 9, things is beginning to go wrong. The problem is not about the output because you got the good result (list = {9,8,7,6,5,4,3,2,1,0}, but your simple for loop break the things.

    for (int i = 0; i < list.size(); i++) {
        result = result  + pow * list.get(i);
        pow = pow * 10;
    }

At the tenth element, pow was 1410065408 which is obviously wrong.

The real question is : Is {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} a valid input ? I can't say since your definition of the problem is missing some precisions. On the other side if you would output an array like @Simon said, this would not be a problem (and you would have one less loop).