[CSES] Weird Algorithm
Weird Algorithm
Task:
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 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 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 \le n \le 10^6$
Input:
3
Output:
3 10 5 16 8 4 2 1
Solutions:
Intuition:This problem is quite straightforward. We just need to follow the requirements until reaching the end state. In this context, it's equal to $1$.
Implementation: 1 def helper(n):
2 print(n, end=" ")
3 if n!=1:
4 if n&1:
5 return helper(n*3+1)
6 else:
7 return helper(n//2)
8 a=int(input())
9 helper(a)
10
Analysis:
Time complexity: $O(N)$
Space complexity: $O(1)$