1
$\begingroup$

Let $S$ be a sequence of $k$ many numbers. The position of the number in the $S$ matters. In the $S$ there are only $j$ many different numbers are there means $S$ contains many duplicates. Position is a query which needed to be answered, position(i) returns the element at position $i$ in $S$.

Trivial way to store them is using array which will takes $O(S)$ space and position can be solved in $O(1)$ time.

I am looking for a representation that takes $O(j)$ space (or somewhere near to it) and such that position can be solved in $O(1)$(even in more time is also ok)?

Please suggest some papers also.

$\endgroup$
  • $\begingroup$ I don't understand what you need completely but why would a hashset not satisfy your requirements? Btw the array as described by you only works if the numbers are (more or less) consecutive. $\endgroup$ – Daniel Oct 12 '19 at 9:04
  • $\begingroup$ @ Daniel Numbers are different and they are $1,2,\ldots, j$. I am looking for deterministic data str. $\endgroup$ – Shiv Oct 12 '19 at 9:51
  • $\begingroup$ What is the element in position $i$ of a set? Sets do not have order. $\endgroup$ – orlp Oct 12 '19 at 10:32
  • $\begingroup$ @orlp You can see them as a some sequence. $\endgroup$ – I_wil_break_wall Oct 12 '19 at 12:01
1
$\begingroup$

What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.

$\endgroup$
  • $\begingroup$ Ok if space is say $\Omega(K)$ then what is position query time. $\endgroup$ – I_wil_break_wall Oct 12 '19 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.