Deckard loves math. He also loves coding. What he doesn't like is recursion1.

After graduating from Notre Dame with a degree from ACMS2, he's still grinding LeetCode in hopes of securing employment as a software engineer and comes across this tricky recursive problem:

For any given `n`, you can apply one of the two following operations:

1. If `n` is even, replace `n` with `n / 2`.
2. If `n` is odd, replace `n` with either `n + 1` or `n - 1`.

Define a function `f(n)` such that it returns the minimum number of operations required for `n` to become `1`.

Normally Deckard would just sit down, sketch out a solution on paper, and then code up his approach (probably in golang), but he is currently too busy updating PKGBUILDs for Arch Linux, maintaining artoo in the NDLUG IRC channel, and contributing fixes to Alpine Linux.

Therefore, he wants to give you a first crack at implementing this recursive function. Of course, he would like for you to do this as efficiently as possible and will allow you to use any programming language of your choice.

#### LeetCode¶

This programming challenge is based on 397. Integer Replacement from LeetCode.

## Input¶

You will be given a series of input integers `n` (one per line) that need replaced (one at a time).

### Example Input¶

``````8
7
4
``````

## Output¶

For each input `n`, perform the operations described above and output the minimum number of replacements required for `n` to become `1`.

For each output, prefix the number of replacements with the input test case number.

### Example Output¶

Here is the output for the example input above:

``````1. 3
2. 4
3. 2
``````

Note: If `n` is already `1`, then `0` operations are required.

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(log(N))`, where `N` is the integer to replace. Space Complexity `O(N)`, where `N` is the integer to replace.

Your solution may be below the targets, but it should not exceed them.

## Submission¶

``````\$ cd path/to/cse-30872-su24-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge10               # Create and checkout challenge10 branch

\$ \$EDITOR challenge10/program.cpp           # Edit your code

\$ git commit -m "challenge10: done"         # Commit your changes

\$ git push -u origin challenge10            # Send changes to GitHub
``````

To check your code, you can use the `.scripts/check.py` script or curl:

``````\$ .scripts/check.py
Checking challenge10 program.c ...
Result Success
Time 0.06
Score 6.00 / 6.00

\$ curl -F source=@challenge10/program.cpp https://dredd.h4x0r.space/code/cse-30872-su24/challenge10
{"result": "Success", "score": 6, "time": 0.06438255310058594, "value": 6, "status": 0}
``````

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.

1. Actually, I'm pretty sure he likes recursion. He's weird like that.

2. Really should have been CSE