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

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

$ cd path/to/cse-30872-su23-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-su23/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 teaching assistant.


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

  2. Really should have been CSE