9

This was an interview question, which seems related to Project Euler Problem 14

Collatz conjecture says that if you do the following

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

You ultimately end up with 1.

For instance, 5 -> 16 -> 8 -> 4 -> 2 -> 1

Assuming the conjecture is true, each number has a chain length: The number of steps required to get to 1. (The chain length of 1 is 0).

Now, the problem is given natural numbers n, m and a natural number k, give an algorithm to find all numbers between 1 and n, such that the chain length of those numbers is <= k. There is also the restriction that the chain of any of those numbers must only include numbers between 1 and m (i.e. you cannot go over m).

An easy way is to brute-force it out, and combine that with memoization.

The interviewer said there was an O(S) time algorithm, where S is the number of numbers we need to output.

Does anyone know what it could be?

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
Anony
  • 91
  • 2

1 Answers1

10

I think you can solve this in O(S) by running the process backwards. If you know what k is, then you can build up all of the numbers that halt in at most k steps using the following logic:

  • 1 has a chain of length 0.
  • If a number z has a chain of length n, then 2z has a chain of length n + 1.
  • If a number z has a chain of length n, z - 1 is a multiple of three (other than 0 or 3), and (z - 1)/3 is odd, then (z - 1) / 3 has a chain of length n + 1.

From this, you can start building up the numbers in the sequence starting at 1:

                  1
                  |
                  2
                  |
                  4
                  |
                  8
                  |
                  16
                  | \
                  32 \
                  |   5
                  64  |
                 /|   10
                / 128 | \
               21     20 3

We could do this algorithm using a work queue storing numbers we need to visit and the lengths of their chains. We populate the queue with the pair (1, 0), then continuously dequeue an element (z, n) from the queue and enqueue (2z, n + 1) and (possibly) ((z - 1) / 3, n + 1) into the queue. This is essentially doing a breadth-first search in the Collatz graph starting from one. When we find the first element at depth k, we stop the search.

Assuming that the Collatz conjecture holds true, we'll never get any duplicates this way. Moreover, we'll have found all numbers reachable in at most k steps this way (you can quickly check this with a quick inductive proof). And finally, this takes O(S) time. To see this, note that the work done per number generated is a constant (dequeue and insert up to two new numbers into the queue).

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • I'm curious as to the space complexity of this method. – Null Set Mar 25 '11 at 20:25
  • It's at most 2^n, since each number branches at most twice. I think that it would be all but impossible to get a better bound than this, since it's not yet resolved whether or not this always terminates. – templatetypedef Mar 25 '11 at 20:26
  • "If a number z has a chain of length n and z - 1 is a multiple of three (other than 0 or 1), then (z - 1) / 3 has a chain of length n + 1." - I don't think this is right. In this case, you should have an edge from `4` going to `1` in your tree, because `4 - 1 = 3`. – IVlad Mar 25 '11 at 20:34
  • @IVlad- But 4 - 1 = 3 x 1, so you don't add the edge. By "except for zero or one" I meant "3m for m not equal to zero or one.". So perhaps I should have said "not zero or three." – templatetypedef Mar 25 '11 at 20:39
  • That makes more sense :). I read it as "z - 1 other than 0 or 1". – IVlad Mar 25 '11 at 20:42
  • You also need (z-1)/3 to be odd. i.e z must be even. –  Mar 25 '11 at 21:21
  • Sorry, was AFK. You're totally right and I'll update right now. – templatetypedef Mar 26 '11 at 00:12
  • Your last clause can be rewritten as: If a number z has chain of length n and z = 6*r + 4 (r > 0), then (2*r + 1) has length n + 1. – user515430 Mar 26 '11 at 03:25