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:
For natural numbers, doubling a number always makes it bigger than adding one (except when the number is 1, then it doesn't matter). So adding one is only needed to reach numbers with odd divisors
The number that we need to reach
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 or n->1, working backwards will give us the same result.
There is probably a better way that doesn't use loops, but these are my initial thoughts:
(using JavaScript)
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.That was my idea as well.