Today's challenge comes from user bdowds on CodeWars.
Given a number, return the shortest amount of steps it would take from 1 to land exactly on that number.
A step is defined as:
- Adding 1 to the number: num += 1
- Doubling the number: num *= 2
You will always start from the number 1 and you will have to return the shortest count of steps it would take to land exactly on that number.
Examples:
num == 3 would return 2 steps:
1 -- +1 --> 2: 1 step
2 -- +1 --> 3: 2 steps2 steps
num == 12 would return 4 steps:
1 -- +1 --> 2: 1 step
2 -- +1 --> 3: 2 steps
3 -- x2 --> 6: 3 steps
6 -- x2 --> 12: 4 steps4 steps
Math problems and string problems often require different approaches, so they'll test different areas of your critical thinking ability.
Good luck, happy coding!
Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!
Want to propose a challenge for a future post? Email yo+challenge@dev.to with your suggestions!
Top comments (16)
If you convert the number to binary, the steps are exactly
(
number of 1s
- 1) * 2 +number of 0s
This way we don’t need loops or recursion.
I was about to submit something like that, so have my applause instead 👏🎉
A little more thinking on the problem can really simplify the solution!
(On a side note, I wouldn't extend a native prototype, but that's out of context now 😅)
That was my original version, then I thought writing two functions might confuse people so I changed it into this. It's just for the sake of demonstration and better readability.🤗But you were right, it is a bad habit to extend a native prototype.
Wow this is brilliant! Nice job!
There is probably a better way that doesn't use loops, but these are my initial thoughts:
(using JavaScript)
That was my idea as well.
How would you come to this concept as I have no idea of this concept to far extend. Have you done these type of quest. or this(concept of using modulus) is the only way of solving this problem?
Well, I imagine that there are other ways to solve it. I came to it when I realised that it wasn't a coding problem as much as a maths problem. There are two key things that we know:
Therefore, since we know the number that we need to reach, it is a lot quicker to work backwards (from the number we need to reach) than to make guesses from number 1. Starting from the end, every time we get to an odd number we subtract 1 (the backward of adding one) and every time we get to an even number we divide by 2 (the backward of multiplying by two).
Since we are dividing by 2 every time we can, that'll ensure that we're always taking as few steps as possible.
Since the amount of steps is the same whether we go
1->n
orn->1
, working backwards will give us the same result.Here's some recursion. I think it will work, but I'm not sure since I'm on my phone, I'll test it when I get home.
I wrote two versions of this. The first one I wrote was an exhaustive search. Then I read some answers here and wanted to write up the solution @savagepixie had and compared them. They matched on all the numbers I tested on (up to 200 in the test case).
At first I wasn't convinced that the 'simpler' solution of counting down was gonna work, but I was definitely wrong! It performs way better than my exhaustive search and seems to be just as accurate
Elixir
First time doing anything on Elixir. It was fun :)
Live demo on Paiza.io.
Elixir:
Recursive thinking is fun :)
JS using a bit of bitwise math
(couple of edits to make it cleaner)
Here is the simple solution with Python:
Ruby:
:)
And here goes an ugly one!