Deckard loves math. He also loves coding. What he doesn't like is
recursion^{1}.

After graduating from Notre Dame with a degree from ACMS^{2}, 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:

- If
`n`

is even, replace`n`

with`n / 2`

.- If
`n`

is odd, replace`n`

with either`n + 1`

or`n - 1`

.Define a function

`f(n)`

such that it returns theminimum 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.

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

You will be given a series of input integers `n`

(one per line) that need
replaced (one at a time).

```
8
7
4
```

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.

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.

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**.

To submit your work, follow the same procedure you used for Reading 01:

```
$ 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 add challenge10/program.cpp # Stage your changes
$ 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}
```

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