2
$\begingroup$

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory.

Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers.

Is there a possibility to generate Nth Hamming number with $O(N)$ time and $O(1)$ (constant) memory? Under generate I mean exactly the generator, i.e. you can only output the result and not read the previously generated numbers (in that case memory will be not constant). But you can save some constant number of them.

I see only best algorithm with constant memory is not better than $O(N log N)$, for example, based on priority queue.

But is there mathematical proof that it is impossible to construct an algorithm in $O(N)$ time and $O(1)$ memory?

$\endgroup$
  • $\begingroup$ Why do you consider a priority queue to be of constant memory? $\endgroup$ – Hendrik Jan May 13 '16 at 13:25
  • $\begingroup$ @HendrikJan We can use ln(2), ln(3) and ln(5) for calculating each number, but not in correct sequence. And we can put them in priority queue for autosorting. $\endgroup$ – vladon May 13 '16 at 13:32
  • $\begingroup$ But storing that sequence to be sorted is not constant memory? $\endgroup$ – Hendrik Jan May 13 '16 at 16:05
  • $\begingroup$ @HendrikJan I think (but not sure) that we can limit size of the priority queue to some big but constant value (less than N, of course) $\endgroup$ – vladon May 13 '16 at 16:11
  • 1
    $\begingroup$ Would be interesting. I have given a solution without PQ cs.stackexchange.com/questions/39689/… using three pointers to a list. The PQ is avoided since we only need to take the minimum of three values. Your idea seems to suggest that only a bounded sequence of numbers needs to be stored in that list. $\endgroup$ – Hendrik Jan May 13 '16 at 21:36

Your Answer

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

Browse other questions tagged or ask your own question.