weird-algorithm

Weird Algorithm

CSES easy

Given a positive integer \(n\), repeatedly apply:

if \(n\) is even, set \(n \leftarrow n/2\);
if \(n\) is odd, set \(n \leftarrow 3n+1\).

Print all values of \(n\) from the start until it reaches \(1\).

Solution

We simulate the process iteratively. Start by printing the initial \(n\), then on each step update \(n\) using the even/odd rule and print it. The sequence is conjectured to always reach \(1\) and is called Collatz Conjecture; for this problem, we just perform the simulation until \(n=1\).

Loop simulation

A single while-loop suffices: print, update \(n\), and stop once \(n=1\).

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    cout << n;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3*n + 1;
        }
        cout << ' ' << n;
    }
}

Overflow

Although the input satisfies \(1 \le n \le 10^6\), intermediate values in the sequence can grow above \(10^9\). Use long long to avoid overflow during \(3*n+1\).