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

Question

A friend of mine came across this question in an online Assessment of a company and asked me this question.

An array of integers is given and we have to (possibly) arrange the array such that no two consecutive numbers sum is divisible by 3.

Size of the array n<=10^5.

If no such arrangement is possible then we have to return Not Possible.

I could think of greedily filling integers such that consecutive element sum if not divisible by 3 that will give an O(n^2) solution (BUT I am not sure if greedily filling elements will give the solution here) or I could think of doing a (bruteforce) DFS by looking all possible arrangements but that would be an exponential time solution and certainly won't work here for the given array size condition.

Is there any O(nlogn) or O(n) solution possible for this?

Answer 1

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