CODEWITHSUNDEEP
algorithmlanguage-agnostic
Mohan
Mohan

Reputation: 4829

Count the minimum number of steps to change a number from m to n

I was on interview and was asked to solve this problem:

Given 2 numbers m & n and we need to convert a number m to n with minimum number of the following operations:

  • -1 - Subtract 1
  • *2 - Multiply by 2

For e.g. : if m=4 and n=6, the program should output 2.

  • 1st operation : -1 -> 4-1 = 3.

  • 2nd operation : *2 -> 3 * 2 =6.

As we can Change m (4) to n (6) after 2 operations, the answer is 2.

Now I have no idea what interviewer was expecting from me, also I have no clue what is a proper solution.

Upvotes: 1

Views: 3675

Answers (2)

szarotka
szarotka

Reputation: 41

This is my solution in java

public class Main {

public static void main(String[] args) {
    int m = 3;
    int n = 36;
    int counter = 0;
    float ntemp;

    if (m > n) {
        counter = m - n;
        System.out.println("result: " + counter);
        return;
    }

    while (m != n) {
        ntemp = n;
        while (m < ntemp) {
            ntemp = ntemp / 2;
        }
        if (m < ntemp + 1) {
            m = m * 2;
            System.out.println("*2");
        } else {
            m = m - 1;
            System.out.println("-1");
        }
        counter++;
    }
    System.out.println("result: " + counter);
}
}

Explanation:

Below I consider only cases where m < n, because case for given m >= n is obvious.

1. If 2m > n

In this case

a) if 2(m-1) = n -> end

b) if 2(m-1) < n

After subtract 1 we have too small number.

We can transform inequality:

2(m-1) < n -> m < n/2 + 1

If we have too small number, we have to multiply by 2, but it would be not optimal, because we have to subtract 2*(m-1) times (or 2*(m-2)-1 if n odd number), so it means that it wasn't good idea to substract 1.

Summarizing: For m < n/2 + 1 -> multiply and then subtract

2. If 2m < n and 4m > n

After some operations (one multiplication and some amount of -1) we want to receive result fulfilling condition from step 1.: m < n/2 + 1 (because we have to multiply once again).

We assumed 4m > n - > 2*2*m > n -> 2m > n/2.

When we change notation n/2 = ntemp, we recieve the same condition:

2m > ntemp, so we can get the same conclusions as in step 1.

3. If x*m < n and 2*x*m > n, x-iteger

Every number m we can transform like in step 2. and get the same conclusions.

P.S.: I know it's not formal proof and sorry for my English :)

Upvotes: 4

Rohit Chopra
Rohit Chopra

Reputation: 567

You can Try This:

def convert(m, n): 

    if(m == n): 
        return 0

    # only way is to do 
    # -1(m - n): times 
    if(m > n): 
        return m - n 

    # not possible 
    if(m <= 0 and n > 0): 
        return -1

    # n is greater and n is odd 
    if(n % 2 == 1): 

        # perform '-1' on m 
        #(or +1 on n): 
        return 1 + convert(m, n + 1) 

    # n is even 
    else: 

        # perform '*2' on m 
        #(or n/2 on n): 
        return 1 + convert(m, n / 2) 

# Driver code 
m = 3
n = 11
print("Minimum number of operations :", 
                          convert(m, n))

Upvotes: 1

Related Questions