1330. The Common Factor So Far
For each position i, print the greatest common divisor of the first i
values.
12 18 6 -> 12 6 6
Recomputing from scratch at every position is O(n^2 log). One pass is enough,
because the greatest common divisor is associative: the answer at each position
is the previous answer combined with the new value.
running = gcd(running, value)
Start the running value at 0, not at the first element and not at 1. The
identity here is 0, since gcd(0, x) is x, and starting at 1 would pin every
answer to 1 forever. That is the whole trick and it is worth remembering beyond
this problem.
The sequence never increases, and once it reaches 1 it stays there, so a long input usually settles quickly.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ value ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated non-negative integers.
Output
Print n values separated by single spaces: the greatest common divisor of the first 1, first 2, and so on.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.