Weird Algorithm
Generate the Collatz sequence starting from n and print every value until the sequence reaches 1.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Start from one positive integer \(n\). If the current value is even, divide it by \(2\); otherwise replace it with \(3n + 1\). Print every value in this chain until the sequence reaches \(1\).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
There is no optimization to discover here: the task is simply to simulate the process exactly as described.
Keep printing the current value, then apply one step of the rule. The loop stops once the current value becomes \(1\), and then \(1\) should also appear in the output.
The only practical detail is the numeric type. Even when the input fits comfortably in a 32-bit integer, the intermediate value \(3n + 1\) can grow past that range, so a 64-bit integer is the safe default.
Pseudocode
Natural algorithm flow before dropping to the concrete C++ implementation.
Read \(n\).
While \(n\) is not \(1\):
print \(n\)
if \(n\) is even, replace it by \(n / 2\)
otherwise, replace it by \(3n + 1\)
Print \(1\).
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(k)\), where \(k\) is the length of the produced sequence
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
std::int64_t n;
std::cin >> n;
while (n != 1) {
std::cout << n << ' ';
if (n % 2 == 0) {
n /= 2;
} else {
n = 3 * n + 1;
}
}
std::cout << 1 << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Use a 64-bit integer type so the odd-step update does not overflow.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.