Challenge 10: Deckard's Recursive Replacement

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

After graduating from Notre Dame with a degree from ACMS², 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.

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

Submission¶

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}