Probably the hardest things are the space and time requirements. If you relax e.g. the O(k) time requirement to O(k log k), the problem essentially becomes triv

Probably the hardest things are the space and time requirements. If you relax e.g. the O(k) time requirement to O(k log k), the problem essentially becomes trivial.[1] More generally, though, what solution are you thinking of? (The problem, as stated, is actually fairly difficult! As far as I can tell...) --- [1] See: https://en.wikipedia.org/wiki/Coupon_collector's_problem https://en.wikipedia.org/wiki/Coupon_collector's_problem . The solution is then to draw repeatedly and then check if this card has been drawn.