# Weird Algorithm

Problem Statement -

**Time limit:**1.00 s**Memory limit:**512 MB

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:

3→10→5→16→8→4→2→13→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

**Input**

The only input line contains an integer n.

**Output**

Print a line that contains all values of n during the algorithm.

**Constraints**

1 ≤ n ≤ 10^6

**Example**

Input:

3

Output:

3 10 5 16 8 4 2 1

LOGIC

This problem is based on ** Collatz conjecture **according to which if we are given a positive number n, then, we can get a sequence in which if previous term(let's say n) is even, the next term is n/2. If previous term is odd, next term is 3n+1. The conjecture is that no matter what the value of n, the sequence will always reach 1.

APPROACH

To solve this problem, we will take n as input. Then, we run a while loop until n is not 1 i.e. n is anything but 1. Inside the loop, we check if n is divisible by two, if yes, then next number must be n/2 else next number must be 3n+1. While loop breaks when n is 1.

CODE(C++)

#include <bits/stdc++.h> using namespace std; #define ll long long int int main() { ll n; cin >> n; cout << n << " "; while(n != 1) { if(n%2 == 0){ n = n/2; cout << n << " "; } else{ n = (n * 3) + 1; cout << n << " "; } } cout << endl; }