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.


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
        # If n is even, divide it by 2
        n //= 2

    # Print the current value of n in the sequence
    print(n, end=' ')


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


No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *