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;
}

Recent Posts

See All

Increasing Array

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the

Repetitions

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence.

Missing Number

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given all numbers between1,2,…,n except one. Your task is to find the missing number. Input The first input line contains an integer

©2019 by EduGeekX. Proudly created with Wix.com