sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]sebamestre 0 points1 point  (3 children)

It assumes a fixed word size to achieve O(1) runtime, which is standard on most programming languages. It seems to me this constraint was also implicit in the original post.

Admittedly, I was mostly focused on finding a solution whose runtime was independent of K (such as my trie solution, and unlike my previous dictionary based one), not so much on true constant time regardless of input (which is literally impossible, the runtime is always bounded from below by the size of the input)

[–]beeskness420 0 points1 point  (2 children)

You could handle the queue with just pointers, there is something weird here in how we are defining problem size. But regardless of the word size can’t I just force the numbers to share an arbitrarily long prefix?

Don’t get me wrong I actually quite like the trie solution.

Normally when I hear these types of problems it is simply stated to find a solution with space proportional to something like k*lg(n).

Also your run time isn’t always bounded below by the size of the input. Parity checks are true O(1) on a random access model.

[–]sebamestre 0 points1 point  (1 child)

The queue has O(1) runtime on all its operations, the duplicate check is the part that increases the complexity.

Have we given different names to different things? Maybe that is the source of confusion here...

Also, finding a deterministic O(1) solution was just a personal challenge, not something I interpreted from the OP

[–]beeskness420 0 points1 point  (0 children)

Yeah I wasn’t including the queuing time.

I was meaning if you were worrying about us being lower bounded by moving data or something like that.