Challenge 11: Sussy Dogecoin Transactions

Ever since his graduation, AKK has been devoting more and more time into investing in cryptocurrencies even while working at the NSA.

In particular, his favorite cryptocurrency is Dogecoin. Being the hacker he is, he was able to find an exploit to artificially create Dogecoin via clandestine transactions. This discovery, along with his desire for Fortnite Gift Cards, has naturally led him to the goal of taking advantage of this exploit to acquire unlimited V-Bucks.

Unfortunately, the methods in which he can create his Dogecoin are limited, as he can only double or add one to his current amount, starting at 0. In addition, he needs to minimize the number of transactions he performs so that his actions won't appear sussy and garner unwanted attention. On top of this, in order to purchase the gift cards, he needs to exchange his Dogecoin to match the exact value of them.

More specifically:

Given a value N, the worth (in Dogecoin) of a Fortnite Gift Card, find the minimum number of transactions needed to acquire N Dogecoin starting with none. Valid transactions include either doubling or adding one to the current amount.

An example is shown below. Given a target value N = 7, the minimum number of transactions to acquire 7 Dogecoin when starting from 0 is 5 transactions.

Input¶

You will be given target values to attain, representing gift card values.

Example Input¶

7
8
14
23

Output¶

For each target value, output the minimum number of allowed transactions required to attain that value, as shown below.

Example Output¶

1. Minimum number of doge transactions: 5
2. Minimum number of doge transactions: 4
3. Minimum number of doge transactions: 6
4. Minimum number of doge transactions: 8

Submission¶

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

$ cd path/to/cse-30872-fa22-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 challenge11               # Create and checkout challenge11 branch

$ $EDITOR challenge11/program.cpp           # Edit your code

$ git add challenge11/program.cpp           # Stage your changes
$ git commit -m "challenge11: done"         # Commit your changes

$ git push -u origin challenge11            # Send changes to GitHub

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

$ .scripts/check.py
Checking challenge11 program.cpp ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge11/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge11
{"result": "Success", "score": 6, "time": 0.016405344009399414, "value": 6, "status": 0}