CSES: Weird Algorithm Solution

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.

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

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

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

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

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