Collatz Steps
Medium · rating 1200 · Math, Implementation
Start from a positive integer n. Repeatedly apply: if n is even, halve it; if odd, replace it with 3n + 1. Print how many steps it takes to reach 1.
Constraints: 1 ≤ n ≤ 106
Editorial
Approach
Simulate the process directly, counting iterations until the value reaches 1. Halve on even, apply 3n + 1 on odd. The sequence is guaranteed (empirically, for all tested inputs) to terminate.
n = int(input())
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
print(steps)Complexity
Time: proportional to the number of steps (no closed form). Space: O(1).
Related problems
- Overtime Pay — Medium
- Credit Card Validation — Medium
- Format a Video Length — Medium
- Shift Duration — Medium
- RGB to Hex Color — Easy
- FizzBuzz — Easy