## Problem Statement

Problem Statement Link: CSES 1068: Weird Algorithm Solution Link

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 -> 1

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

## Solution

```
import sys
def linput():
return list(minput())
def minput():
return map(int, sys.stdin.readline().strip().split())
# Get the input value for n
n = int(input())
# Print the initial value of n
print(n, end=' ')
# Continue the loop until n becomes 1
while n != 1:
# Check if n is odd using bitwise AND operator with 1
if n & 1:
# If n is odd, multiply it by 3 and add 1
n = n * 3 + 1
else:
# If n is even, divide it by 2
n //= 2
# Print the current value of n in the sequence
print(n, end=' ')
```

## Explanation

Let’s break down the logic of the solution and understand why it’s correct.

**Input Reading Functions (**`linput`

and`minput`

):

`linput()`

returns a list of integers obtained from the standard input using`minput()`

.`minput()`

reads a line from the standard input, strips leading and trailing whitespaces, splits it into a list of strings, and converts each string to an integer using`map(int, ...)`

. It’s a convenient way to read space-separated integers.

**Main Logic:**

`n = int(input())`

: Read the initial value of`n`

from the user.`print(n, end=' ')`

: Print the initial value of`n`

followed by a space, without moving to the next line.

**Simulation of the Collatz Conjecture Algorithm:**

- The while loop (
`while n != 1:`

) continues until`n`

becomes 1. - Inside the loop:
`if n & 1:`

checks if`n`

is odd by using the bitwise AND operator with 1.- If
`n`

is odd, it multiplies`n`

by 3 and adds 1:`n = n * 3 + 1`

. - If
`n`

is even, it divides`n`

by 2:`n //= 2`

. - The current value of
`n`

is printed on the same line with a space, showing the sequence of numbers in the Collatz conjecture.

**Correctness:**

- The algorithm correctly follows the rules of the Collatz conjecture, where if
`n`

is even, it’s divided by 2, and if it’s odd, it’s multiplied by 3 and 1 is added. - The loop continues until
`n`

becomes 1, and the sequence of numbers is printed at each step.

**Efficiency:**

- The use of bitwise AND (
`n & 1`

) efficiently checks whether`n`

is odd, as the least significant bit of an odd number is always 1 in binary. - The use of
`//= 2`

for division by 2 is an efficient way to perform integer division.

In summary, the solution correctly implements the Collatz conjecture algorithm, efficiently handling odd and even numbers, and prints the sequence until `n`

becomes 1.

You can find our more blogs here.

Want to know the top places to visit in Jaipur? Read this