CODEWITHSUNDEEP
arraysalgorithm
Andy
Andy

Reputation: 58

algorithmic: the minimum number of operations form M to N with only three operations

Two positive numbers M and N are given, now you can only do one the following three manipulation to M as follows: plus 1, sub 1, or multiply by 2.

each time you can choose any of the three operations.

Input: M = 2, N = 3 Output: 1 (2 + 1)

Input: M = 2, N = 5 Output: 2(2 * 2, + 1)

Return the minimum number of operations needed to display the number Y.

BFS can be used here, but it has a high time complexity, maybe O(2^n). As for a simpler problem, leetcode991 using greedy algorithmic. so can any one give a similar one.

Upvotes: 1

Views: 620

Answers (1)

Dave
Dave

Reputation: 9085

At each step you're at a number. Think of this in reverse as a trip from N to M. At position x calculate the following:

1. abs(x-M)
2. for even x, 1 + abs(x/2-M)
3. for odd x, 2 + abs((x+1)/2-M)
4. for odd x, 2 + abs((x-1)/2-M)

Choose the option with the smallest result, note the operation(s), and repeat. Stop if you ever choose the first option.

E.g., M=17, N=39

x=39, the (1,2,3,4) tuple is (22, n/a, 4, 3), so we choose the fourth option.
x=19, we have (2, n/a, 8, 9), so we choose the first option

Now we reverse these to get: 17+1+1 = 19; 19*2+1 = 39

This takes log time.

Upvotes: 2

Related Questions