25

The following was an interview questions that I am practicing to solve, however my solution was not correct. Did someone has a clue?

Two integer variables L and R are initially equal to 0 and 1 respectively (i.e. L = 0 and R = 1).

The values of these variables can be manipulated using the following operations: operation 'L' is the assignment L = 2*L-R, operation 'R' is the assignment R = 2*R-L.

Given an integer N we want to find what is the shortest sequence of such operations necessary to make either L or R equal to N. For example, given N = 21, the following sequence of operations:

(initially L = 0, R = 1),
L = 2*L-R (makes L = -1, R = 1),
L = 2*L-R (makes L = -3, R = 1),
R = 2*R-L (makes L = -3, R = 5),
L = 2*L-R (makes L = -11, R = 5),
R = 2*R-L (makes L = -11, R = 21)

makes one of the variables (namely R) equal to N (i.e. after the last operation N = R = 21). This sequence consists of 5 operations and there is no shorter sequence that would make either L or R equal 21.

Write a function int interval_unfold_count(int n);

that returns the length of the shortest sequence of operations resulting in either L or R being equal to N. For example, given N = 21 the function should return 5.

The function should return -1 if no such sequence exists. The function should return 0 if no operations are required.
The following was my initial solution:

int interval_unfold_count ( int n ) {
    long l = 0, r = 1;
    long sequence = 0, i = 0;
    if (l == n || r == n )
        return 0;
    while (true){
        i++;
        if (l == n || r == n )
            break;
        if (abs(n-abs(r)) > abs(n-abs(l)) ){
            r = 2*r - l;
            sequence++;
        }
        else if (abs(n-abs(l)) >= abs(n-abs(r))) {
            l = 2*l - r;
            sequence++;
        }
        if ( sequence > 32){ //in each sequence the absolute of l or r will always be larger than previous value
        // so at most after 32 space it will use all the 32 bit space of the integer.
        //after more than 32 iterations, it will cause overflow
            sequence = -1;
            break;
        }
    }
    return sequence; 
}

I found out that my solution logic was wrong. Does someone has any idea how to solve this? What is the correct if/else condition to determine whether we should multiply the first or the second value?

24 accepted

If the value is 0 or 1 the solution is 0.

otherwise

For positive values I think the solution is the binary length of value - 1. So:

value = 21

value - 1 = 20

binary = 10100

solution 5

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;
        }
        else
        {
            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)) : 
    0;

The reasoning

  • 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!
  1. 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

(where [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 :-) )

1

Although @Varun mentioned it in the comments of the question, use a breadth-first search like A*.