Solution - Weird Algorithm - CSES Problem Set

• • 
    

• Weird Algorithm

  #include <iostream>

  using namespace std;

  
  

  int main() {

     

      long long int n;

      cin >> n;

      cout <<n<<" ";

  
  

      while(n>1){

  
  

          if(n%2==0){

             

              n=n/2;

              cout <<n<<" ";

  
  

          }else{

  
  

              n=(n*3)+1;

              cout <<n<<" ";

  
  

          }

      }

      return 0;

  }

  • 
    

  • CSES Problem Set

    Weird Algorithm

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

Consider an algorithm that takes as input a positive integer 

n

$n$. If n

$n$ is even, the algorithm divides it by two, and if n

$n$ is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n

$n$ is one. For example, the sequence for n=3

$n=3$ is as follows:

3→10→5→16→8→4→2→1$$3\to 10\to 5\to 16\to 8\to 4\to 2\to 1$$

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

Input

The only input line contains an integer n$n$.

Output

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

Constraints

• 1≤n≤106$1\le n\le {10}^6$
  

Example

Input:
3

Output:
3 10 5 16 8 4 2 1