If we take sum of all N numbers there can be three conditions:

• sum is divisible by 3 :
  In this case answer will be N

• sum%3==1 :
  In this case there can be two possible answer.

a>> if there exists any number X where X%3==1, then we can uncount X and the rest of the sum will be divisible by 3. so the answer will be N-1

b>> if there do not exist any number X where X%3==1, then there must exist two number X1,X2 where X1%3==2 and X2%3==2. we can remove those two numbers from the array and the answer will be N-2

• sum%3==2 :
  In this case there can be two possible answer.

a>> if there exists any number X where X%3==2 , then we can remove X from the array and the sum of the remaining numbers will be divisible by 3. so the answer will be N-1

b>> if there do not exist any number X where X%3==2 , then there must exist two number X1,X2 where X1%3==1 and X2%3==1. We can remove those two numbers and the answer will be N-2

note : we can keep count how many numbers gives remainder 1 and how many of them gives remainder 2 after dividing with 3. we dont need to think about the numbers which are already divisible by 3. because for any two number X and Y where Y is divisible by 3, if X%3==a then (X+Y)%3==a

time complexity : O(N)