Teaching Kids Programming – Minimum Number of Operations to Target Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given positive integers start and end, return the minimum number of operations needed to convert start to end using these operations:

1. Decrement by 1
2. Multiply by 2

Constraints
0 ≤ start, end < 2 ** 31
Example 1
Input
start = 5
end = 9
Output
2
Explanation
We can multiply 5 to get 10 and then subtract 1 to get 9

Example 2
Input
start = 26
end = 48
Output
3
Explanation
We can subtract 26 twice to get 24 and then multiply 2 to get 48.

Example 3
Input
start = 3
end = 10
Output
3
Explanation
We multiply 2 to get 6, subtract 1 to get 5, and then multiply 2 to get 10.

Try doing the operations in reverse from end to start.

Reverse Operations

We can reverse the operations, by converting from end to start. If the current number is odd, we can only increment it – otherwise it is better to make it half.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minNumberOfOperationsToTarget(self, start, end):
        ans = 0
        while end > start:
            if end & 1:
                end += 1
            else:
                end //= 2
            ans += 1
        return ans + start - end;

class Solution:
    def minNumberOfOperationsToTarget(self, start, end):
        ans = 0
        while end > start:
            if end & 1:
                end += 1
            else:
                end //= 2
            ans += 1
        return ans + start - end;

When the number is less than the target, we can keep incrementing it to reach the destination.

We can also implement using Recursion.

1
2
3
4
5
6
7
8

class Solution:
    def minNumberOfOperationsToTarget(self, start, end):
        if end <= start:
            return start - end
        if end & 1: # odd number
            return 1 + self.solve(start, end + 1)
        # even number
        return 1 + self.solve(start, end // 2)

class Solution:
    def minNumberOfOperationsToTarget(self, start, end):
        if end <= start:
            return start - end
        if end & 1: # odd number
            return 1 + self.solve(start, end + 1)
        # even number
        return 1 + self.solve(start, end // 2)

The time complexity for both implementations is O(LogN) if the start is smaller than the target – as we can divide the target by two in most cases.

–EOF (The Ultimate Computing & Technology Blog) —