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 aFortnite Gift Card, find theminimum number of transactionsneeded to acquire`N`

Dogecoin starting with none. Valid transactions include eitherdoublingoradding oneto 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.

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

```
7
8
14
23
```

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

```
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
```

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

Time Complexity |
`O(N)` , where `N` is the target number of Dogecoin. |

Space Complexity |
`O(N)` , where `N` is the target number of Dogecoin. |

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 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}
```

Once you have committed your work and pushed it to GitHub, remember to
create a **pull request** and assign it to the appropriate **teaching
assistant** from the Reading 06 TA List.