Generate the Collatz Sequence From a Positive Integer Down to 1
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
The Collatz process starts from a positive integer `n` and repeatedly applies one rule to the current number: if it is even, divide it by 2; if it is odd, multiply it by 3 and add 1. The process stops as soon as the current number is 1. The Collatz conjecture states that the process reaches 1 from every positive starting number. It has not been proven, but it has been checked far beyond the inputs used here.
Write a function that runs the process and returns every number it visits, starting with `n` and ending with `1`.
### Function Signature
```python
def collatz_sequence(n: int) -> list[int]:
```
### Rules
- The first element is `n` and the last element is `1`. Every other element is obtained from the element before it by the rule above.
- `1` appears exactly once, as the last element: the process stops at the first `1` it reaches and does not continue.
- For `n = 1`, return `[1]`.
### Constraints
- `1 <= n <= 10^6`
- For every such `n` the process reaches `1`, and the returned list has at most 525 elements.
- Intermediate values can exceed `2^31 - 1`: the largest value reached from any starting number in this range is 56,991,483,520. All values stay far below `2^53`.
### Examples
**Example 1**
```text
Input: n = 6
Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]
```
6 is even, so the next value is 3. 3 is odd, so the next is 10. The process continues through 5, 16, 8, 4 and 2, and stops at 1.
**Example 2**
```text
Input: n = 1
Output: [1]
```
The process is already at 1, so no rule is applied.
**Example 3**
```text
Input: n = 7
Output: [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
```
Overview: Write a function that runs the Collatz process from a positive integer, halving even values and replacing odd values with three times the value plus one, and returns every number visited until reaching 1. It tests loop termination, edge cases such as a start of 1, and intermediate values beyond 32-bit range.
The Collatz process starts from a positive integer `n` and repeatedly applies one rule to the current number: if it is even, divide it by 2; if it is odd, multiply it by 3 and add 1. The process stops as soon as the current number is 1. The Collatz conjecture states that the process reaches 1 from every positive starting number. It has not been proven, but it has been checked far beyond the inputs used here.
Implement `collatz_sequence(n)`, which runs the process and returns every number it visits, in the order visited, starting with `n` and ending with `1`.
### Rules
- The first element is `n` and the last element is `1`. Every other element is obtained from the element before it by the rule above.
- `1` appears exactly once, as the last element: the process stops at the first `1` it reaches and does not continue.
- For `n = 1`, return `[1]`.
### Constraints
- `1 <= n <= 10^6`
- For every such `n` the process reaches `1`, and the returned list has at most 525 elements.
- Intermediate values can exceed `2^31 - 1`: the largest value reached from any starting number in this range is 56,991,483,520. All values stay far below `2^53`. Store the elements as 64-bit integers (`long` in Java, `long long` in C++); JavaScript numbers represent them exactly.
### Examples
**Example 1**
```text
Input: n = 6
Output: [6, 3, 10, 5, 16, 8, 4, 2, 1]
```
6 is even, so the next value is 3. 3 is odd, so the next is 10. The process continues through 5, 16, 8, 4 and 2, and stops at 1.
**Example 2**
```text
Input: n = 1
Output: [1]
```
The process is already at 1, so no rule is applied.
Constraints
- 1 <= n <= 10^6
- For every such n the process reaches 1, and the returned list has at most 525 elements.
- Intermediate values can exceed 2^31 - 1: the largest value reached from any starting number in this range is 56,991,483,520. All values stay far below 2^53 (use long in Java and long long in C++).
Examples
Input: (1,)
Expected Output: [1]
Explanation: Minimum valid input: already at 1, so no rule is applied; 1 element.
Input: (2,)
Expected Output: [2, 1]
Explanation: Smallest even start and smallest power of two above 1: a single halving; 2 elements.
Hints
- The next value depends only on whether the current value is even or odd, so the whole list is determined one element at a time.
- Decide when to stop before applying the rule again: 1 must appear exactly once, at the end, and n = 1 needs no step at all.
- Check how large an intermediate value can get for inputs in range, and pick an element type wide enough to hold it.