If the value is 0 or 1 the solution is 0.
For positive values I think the solution is the binary length of value - 1. So:
value = 21
value - 1 = 20
binary = 10100
You can note that, reading the binary from greatest to smallest, it's RLRLL (each 1 is R, each 0 is L). You have to subtract 1 because R is = 1 at the start. This will work for positive numbers (I think/hope) (tested 0... 100000).
For negative number do as previsiously said, but instead of value - 1 use -value. So
value = -21
-value = 21
binary = 10101
solution = 5
For negative you can't use the binary representation you calc with -value to find the right R and L combination. You have to do something different (but the solution is still right, they asked for the number of steps, not for the exact sequence :-) )
This code will find the "right" combination of L and R for a range of number, checking if my idea is right. It's C# because I'm better with C# than with C++ and, in the end, implementing the algorithm is trivial when you know what you are looking for. It WON'T return the asked length (but it's very easy, simply return bitValue.Length without checking it). For negative numbers it's based on the fact that they are represented in 2 complement in memory. The Convert.ToString converts a number in binary form. For negative values I truncate the "complemented" 1s at the beginning, until I find a 0 (-21 = 11111111111111111111111111101011, truncating the beginning 1s you get 01011)
for (int myInt = -100000; myInt < 1000000; myInt++)
string binValue = myInt != 0 && myInt != 1 ? Convert.ToString(myInt - 1, 2) : String.Empty;
var length = myInt != 0 && myInt != 1 ? Math.Ceiling(Math.Log(myInt > 0 ? myInt : -myInt + 1, 2)) : 0;
if (myInt < 0)
binValue = binValue.Substring(binValue.IndexOf('0'));
if (length != binValue.Length)
throw new Exception("Log formula is wrong");
if (myInt < 0 && binValue.Length != Convert.ToString(-myInt, 2).Length)
throw new Exception("Negative value formula is wrong");
int l = 0, r = 1;
for (int i = binValue.Length - 1; i >= 0; i--)
if (binValue[i] == '1')
r = r * 2 - l;
l = l * 2 - r;
if (myInt > 0 && r != myInt || myInt <= 0 && l != myInt)
throw new Exception("General formula is wrong");
So in the end the value to return is:
var length = myInt != 0 && myInt != 1 ?
Math.Ceiling(Math.Log(myInt > 0 ? myInt : -myInt + 1, 2)) :
- We know that L <= 0 an R >= 1 always (this for how they are built)
- at the n "round", R <= 2^n (easy to demonstrate, always use the R formula)
- if myInt = 0 or 1, the solution is trivial (0)
- if myInt > 1, clearly you'll need at least log2(myint) rounds (rounded up). So myInt = 2 at least 1 round, myInt = 3 or 4 at least 2 rounds....
- my solution has that number of rounds, so it's optimal (at least for positive numbers... I'll ignore negative numbers).
Now a little demonstration on the fact that my solution is correct, and that being long exactly length step, it's optimal. I'm doing it for myInt > 1, because it's easier with positive numbers. For negative numbers it's a little more complex but I'm quite sure the steps are nearly the same.
We first want to demonstrate that R(n)-L(n) = 2^n at any step
With Mathematical Induction (P(0) is true and for any P(n-1), P(n-1) => P(n), then P(n) is true)
1. R(0)-L(0) = 2^0 = 1 True!
2. If we have that R(n-1)-L(n-1) = 2^(n-1)
If we select the rule R
3a. L(n) = L(n-1)
3b. R(n) = 2R(n-1) - L(n-1) = R(n-1) + R(n-1) - L(n-1) = R(n-1) + 2^(n-1)
3c. R(n) - L(n) = R(n-1) + 2^(n-1) - L(n-1) = 2^(n-1) + 2^(n-1) = 2^n True!
- is True, 2. => 3abc. so it's True.
the same can be done with rule L
Now we want to show that when we, at step n, select the rule R, R increases by 2^(n-1)
So, for example, R(5) = R(4) + 2^4
R(n) = 2R(n-1) - L(n-1) = R(n-1) + R(n-1) - L(n-1) = R(n-1) + 2^(n-1)
R(n) - R(n-1) = R(n-1) + 2^(n-1) - R(n-1) = 2^(n-1) True!
the same can be done with rule L
So now we know that if at step n we select the rule R, R will increase by 2^(n-1)
We can see that there is a relationship between a searched for number > 1, R and the binary (base 2) representation of the number.
if intNum is the "target" value of R, we need to increase R by
x = intNum - R(0) = intNum - 1
So we have to find the "right" combination of the R rules that will increase R(0) by x.
Any integer base 10 number > 0 can be represented in base 2 in this way:
[0-1] * 2^0 + [0-1] * 2^1 + [0-1] * 2^2 + [0-1] * 2^3 + ... + [0-1] * 2^n
[0-1] means that you can have a 0 or a 1]).
and we know that each time we select the R rule we increase R by 2^(n-1). The relationship is clear:
- For each 1 of the binary representation of x, we select the R rule.
- For each 0 of the binary representation of x, we select the L rule.
Done. (ok... this isn't exactly a mathematical demonstration, but I'm quite sure this is enough for you that are reading this :-) )