Given a non-empty sequence of non-negative integers, output any permutation of it in which no two adjacent elements have a sum that is divisible by 3. If it is impossible, either crash the program, return an empty sequence, or output nothing.
The asymptotic time complexity must be linear in the size of the input sequence.
Example Input and Possible Output:
1,2,3 -> 1,3,2 9,5,3,6,2 -> 9,5,3,2,6 5,6,15,18,2 -> 6,5,15,2,18 1,2,3,4,5,6,7,8,9,10 -> 3,1,6,4,7,10,9,2,5,8 6,1,6,6 -> no solution 4,3,7,6,6,9,0 -> no solution