@Ahmad: This is known as a Collatz Sequence. It is hypothesized that the sequence will eventually reach 1 for every starting number N. So here is an algorithm to find where they meet, using O(1) space: 1. Generate each sequence and count the number of iterations required to reach 1. You need not store the sequences. Call the iteration counts C1 and C2. 2a. If C1 >= C2, restart sequence 1 and iterate it for C1 - C2 steps. Then restart sequence 2 and iterate the two sequences simultaneoulsy until they agree. 2b. If C2 > C1, restart sequence 2 and iterate it for C2 - C1 steps. Then restart sequence 1 and iterate the two sequences simultaneously until they agree. Dave
On Thursday, July 26, 2012 12:39:44 PM UTC-5, Ali Ahmad Ansari wrote: > Given a number N, generate a sequence S such that > S[ 0 ] = N > S[ i+1 ] = (3 * S[ i ] + 1) / 2 if S[ i ] is odd, > = S[ i ] / 2, if S[ i ] is even, > till you reach 1. > For example for N = 5, the sequence is 5, 8, 4, 2, 1 > Given two numbers 20 and 35, generate the sequence S for A > and B, and find the number where the two sequences meet. > a.20 > b.30 > c.35 > d.40 > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lBJL5zrohL8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
