Collatz
SRM 130 · 2003-01-25 · by brett1479
SRM 130 · 2003-01-25 · by brett1479
Problem Statement
Problem Statement
The Collatz Problem asks whether the following function will reach 1 for all positive k if we keep applying it:
So for k = 20 this function required 7 applications of the function to reach 1. Given anint k return the number of applications required to reach 1. Topcoder has ensured that the number of applications will be less than 1000 and that any temporary value will not overflow a 32-bit integer.
{ if k is odd : 3*k +1
f(k)= {
{ if k is even : k/2
For example, lets say you were given k = 20:f(20) = 10 First application f(10) = 5 Second application f(5) = 16 Third application f(16) = 8 Fourth application f(8) = 4 Fifth application f(4) = 2 Sixth application f(2) = 1 Seventh application
So for k = 20 this function required 7 applications of the function to reach 1. Given an
Constraints
- k will be between 2 and 100000 inclusive.
- The return value will be less than 1000.
Examples
0)
20 Returns: 7
The example from above
1)
13 Returns: 9
2)
1000 Returns: 111
3)
99999 Returns: 226
4)
9999 Returns: 91
7)
2 Returns: 1
Just a single application required
8)
5 Returns: 5
5*3+1 = 16 16/2 = 8 8/2 = 4 4/2 = 2 2/2 = 1
Submissions are judged against all 26 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Collatz with a public method int numSteps(int k) · 26 test cases · 2 s / 256 MB per case