Given an array, arr[] of integers. The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

Expect time complexity O(N) and the interviewer said that it can be done in only one/two traversal(s)(sorry I don't remember it clearly, it was quite sometime ago).

Expected space complexity O(1).

there are 3 types of queries

0 X add a number X, 1 X remove the number X (X always exist), 2 X return the number of subsets that sum to X,

0<=X<=10^3 0<=number of queries <=10^3

I tried to implement this using the knapsack approach but its bound to give TLE

any suggestions? Any help would be appreciated

I was giving this round https://mirror.codeforces.com/contest/1542 and wasn't able to solve problem B. Though after just a small hint I was able to solve it but I can't get over the fact that I wasn't able to approach this question . are the some good resources for constructive algorithm questions or its just natural for some people ? if there are some good resources please do share them. It's not just the mentioned contest I want to improve ability to solve constructive algorithm questions in general.

thanks in advance