TopCoder Statistics - Problem Statement

Problem Statement

The Collatz Problem asks whether the following function will reach 1 for all positive k if we keep applying it:

      { 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 int 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.

Definition

Class:: Collatz
Method:: numSteps
Parameters:: int
Returns:: int
Method signature:: int numSteps(int k)
(be sure your method is public)

Constraints

k will be between 2 and 100000 inclusive.
The return value will be less than 1000.

Examples

20

Returns: 7

The example from above
13

Returns: 9
1000

Returns: 111
99999

Returns: 226
9999

Returns: 91
77031

Returns: 350
99999

Returns: 226
2

Returns: 1

Just a single application required
5

Returns: 5

5*3+1 = 16 16/2 = 8 8/2 = 4 4/2 = 2 2/2 = 1
734

Returns: 46
10992

Returns: 42
99999

Returns: 226
100000

Returns: 128
73742

Returns: 94
24533

Returns: 51
34555

Returns: 248
23456

Returns: 100
98765

Returns: 53
18283

Returns: 92
77671

Returns: 231
8

Returns: 3
10000

Returns: 29
8

Returns: 3
10000

Returns: 29
8

Returns: 3
10000

Returns: 29

Statistics

Problem Statement for "Collatz"

Problem Statement

Definition

Constraints

Examples