DSA sheet / Introductory
Weird Algorithm
The problem in brief
You get one integer n. Repeatedly apply a simple rule (halve it if it is even, otherwise triple it and add one) and print the whole sequence of values until the process reaches 1. n goes up to a million.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1068.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Nothing clever is needed here. The statement literally tells you what to do, so the job is to translate it into a loop that runs until a condition is met.
-
Which loop fits when you do not know in advance how many steps there will be? Think
while, and think about what the stopping condition is. -
Try n = 999999 on paper for a few steps. Does any value in the sequence get larger than the starting n? How large can it get, and does that fit in a 32-bit integer?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Start by checking that the problem is really just a simulation: no input is asked to be optimised, no choice is made, every step is forced. When there is nothing to decide, the only real question is “what can go wrong in the code I write?”.
The brute force here is the solution, so ask instead about the machine: how many steps, and how big do the numbers get? Values in the sequence can climb far above the start: for some starts below a million the peak is in the tens of billions, well past 2^31 - 1, and that is the trap. Whenever a rule multiplies (here by 3), pause and ask which integer type holds the worst case.
The transferable habit: before writing any loop, name its stopping condition and the largest value any variable can take.
Intuition
Think of the number as a token hopping along a track. Even numbers hop down by half, odd numbers hop up and to the right, then land on an even number next turn (3n + 1 of an odd n is even). So the sequence tends to wander up a bit and then fall. Nobody has proved it always reaches 1 for every n, but for every n allowed here it does, and it does so quickly.
Approach
- Read n into a 64-bit integer.
- Print n, then loop while n is not 1: apply the rule, print the new value.
- Separate the numbers with spaces on one line.
Pitfalls: use a 64-bit type (long long, Java long, Python integers are already unbounded, JavaScript numbers are exact up to 2^53 which is plenty here). Build the output in one buffer instead of printing one number per call; the sequence can have hundreds of terms, and many small writes are slow in some languages.
Complexity
The number of steps is the sequence length, which is a few hundred for every n up to a million (the longest below a million is 524 steps). Time is proportional to that length, memory is constant apart from the output.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
string out = to_string(n);
while (n != 1) {
n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
out += ' ';
out += to_string(n);
}
cout << out << "\n";
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
out = [n]
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
out.append(n)
print(" ".join(map(str, out)))
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(in.readLine().trim());
StringBuilder sb = new StringBuilder();
sb.append(n);
while (n != 1) {
n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
sb.append(' ').append(n);
}
System.out.println(sb);
}
}let n = Number(require('fs').readFileSync(0, 'utf8').trim());
const out = [n];
while (n !== 1) {
n = n % 2 === 0 ? n / 2 : 3 * n + 1;
out.push(n);
}
console.log(out.join(' '));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).