If I have points on a line at positions (0), (1), (3), and (7) the set of intervals between any two points is the set of integers (1,2,3,4,6,7). In-general, a set of N unique integers can be represented by approximately log(N) points on a line. However, I want to represent a contiguous set of integers (1 to N) this way, which seems to be a bit more challenging. So far I have only come up with sequences that solve this problem with around 2*√N points and I think that might be the hard lower bound.

If I loosen the requirements of the problem to say that I want to represent all integers from 1 to N or their multiples, more efficient sequences are possible. In fact, this can always be done with just two points: (0) and (N!). However, calculating N! is slower than O(nlogn) which is slower than the previous solution.

Is there an algorithm that can generate a sequence of points on a line that solves that second problem and is faster than O(√N)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.