Quick Notes
Random thoughts, quick insights, and small discoveries worth remembering. A collection of bite-sized knowledge and spontaneous observations.
2 notes
•
Latest: August 2025
<div class="note-item"
data-title="day #1 - weird algorithm"
data-content="day #1 - weird algorithm
problem
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 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1
your task is to simulate the execution of the algorithm for a given value of n.
input
the only input line contains an integer n.
output
print a line that contains all values of n during the algorithm.
constraints
1 \le n \le 10^6
example
input:
3
output:
3 10 5 16 8 4 2 1
solution #1
this is my first time trying cs problems from marine engineering background. intuitively, i implemented them straight-forwardly using while loop and if-else conditional statement. i expected them to be that straightforward since it’s introductory problems, but turn out it’s not as simple as i tought earlier.
#include <iostream>
int main()
{
int n;
std::cin >> n;
while (n != 1)
{
std::cout << n << " ";
if (n % 2 == 0)
n /= 2;
else
n = 3 * n + 1;
}
std::cout << n << " ";
return 0;
}
however, to my surprise, it resulted in
failure in some test case. which result in my suspicioun about
the data type that i used
printing during computation that makes the program slow
here’s how i deduced the failure. initially, i was confident that it would work, but since it result in failed, i had to check the test case and compile the implementation. here’s the result
and as you can see, after 932774453 it flips into negative value instead, and make me realized that perhaps int data type wasnt enough because it seem to overflowed the 32-but int data type. hence, i tried to change this in my next attempt.
now, about the time limit, i’ve used std::cout in each computation which as i’ve read further, it seemed that calling it in each loop result in costly time limit since they execute multiple buffer flushes. that’s why, in the next attempt, i tried to batch the operation.
solution #2
#include <iostream>
#include <vector>
int main()
{
long long n;
std::cin >> n;
std::vector<long long> sequence;
while (n != 1)
{
sequence.push_back(n);
if (n % 2 == 0)
n /= 2;
else
n = 3 * n + 1;
}
sequence.push_back(1);
// print all at once
for (long long num : sequence)
{
std::cout << num << " ";
}
return 0;
}
now, the approach work better and as i’ve tried to compile prior submitting it and input the previously failed test case, it resulted in following:
and after submitting:
key note (attempting cses for the first time)
in c++, it uses standard library, iostream to read the input via cin and output the expected output mentioned in the problem via cout.
keep an eye on the time limit and memory expectation for the problem’s constraints.
the return value of the main function doesnt matter.
further readings
as it turns out, the problem is an unsolved problems in mathematics, that asks whether repeating 2 simple arithmetic will eventually transform any positive integer into 1.
veritasium
wikipedia
photo by andrea leopardi on unsplash
"
data-tags="cses "
data-date="2025-08-25">
Day #1 - Weird Algorithm
Day #1 - Weird Algorithm
Introduction to Trigonometry
When I was in school, I always tought trigonometry in term of triangle. Terminologically, it is, since the word trigonometry is derived from word trigonon (triangle (tri- = three, gonia...
</div>