337. GCD Between Links
A bead maker threads positive whole numbers onto a chain, and head is the first bead. To make the chain look balanced, a spacer bead must be threaded between every two neighbouring beads. The number written on a spacer is the greatest common divisor of the two numbers on the beads it separates, that is, the largest positive integer that divides both.
Insert one spacer node between each pair of adjacent nodes and return the head of the longer chain. The original nodes keep their order, no spacer is added before the first or after the last node, and a chain with fewer than two nodes is returned as it is. Compute each divisor from the original neighbours, not from other spacers. Values reach one billion and the chain can have 100,000 nodes, so counting down to find a divisor is too slow.
Example 1
- Input:
- head = [24,36,7,91,65]
- Output:
- [24,12,36,1,7,7,91,13,65]
- Explanation:
gcd(24,36)=12, gcd(36,7)=1, gcd(7,91)=7, gcd(91,65)=13, giving 24, 12, 36, 1, 7, 7, 91, 13, 65.
Example 2
- Input:
- head = [14,14,21]
- Output:
- [14,14,14,7,21]
- Explanation:
gcd(14,14)=14 and gcd(14,21)=7, giving 14, 14, 14, 7, 21.
Constraints
0 ≤ chain length ≤ 105
1 ≤ node value ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log V)
- Space
- O(1)