Arrange an integer array such that no two consecutive numbers sum is divisible by 3

yes there exists O(n) solution:

1. First divide all element into 3 buckets, element x will belong to bucket x mod 3
2. Now we can use greedy strategy: notice that elements from buckets 1 and 2 cannot be neighbors, same for elements from bucket 0 and 0
3. We can put all elements from bucket 1 into the answer, followed by one element from bucket 0 and all elements from bucket 2
4. Now all that's left is some elements from bucket 0 which we can put between two elements of bucket 1 or two element from bucket 2
5. Of course there are some corner cases for which solution is impossible