Be the first user to complete this post

  • 0
 Add to List
Beginner

376. Collatz Conjecture - Steps to transform Number to 1

The Collatz conjecture is a conjecture in mathematics which states that no matter what value of Positive Number N, If the below sequence is followed then, the sequence will always reach 1.

  1. If N is even then do N = N/2
  2. If N is odd then do N = 3*N+1
  3. If N is 1 then stop else keep performing step 1 and step 2.

Example:

N = 7
Sequence: 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 ->4 ->2 -> 1

N = 6
Sequence: 6 -> 3 -> 10 -> 5 -> 16 -> 8 ->4 ->2 -> 1

Approach: Recursion

N = N/2 if N is even and N = 3*N+1  if N is odd will be 2 recursive equations and if base case would be if N =1. 

Output:

->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
Total Steps to transform N = 7 to 1: 16

->6->3->10->5->16->8->4->2->1
Total Steps to transform N = 6 to 1: 8

Related Problems: