Minimum Operations To Convert Number - Leetcode Solution

Problem Statement

Given a positive integer n, you can perform any of the following 3 operations:

1. Subtract 1 from it. (n = n - 1)
2. If it is divisible by 2, divide by 2. (if n % 2 == 0, then n = n / 2)
3. If it is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3)

Calculate the minimum number of operations required to reduce n to 1.

Example:

Input: n = 10

Output: 3

Explanation:

You can perform the following operations:

10 - 1 = 9
9 / 3 = 3
3 / 3 = 1

Therefore, the minimum number of operations required is 3.

Solution

Approach:

This problem can be solved efficiently with the help of dynamic programming.

To calculate the minimum operations required to reduce n to 1, we will use an array dp[n+1]. Where dp[i] will represent the minimum number of operations required to reduce i to 1.

For any given i, we can calculate its minimum number of operations to 1 using the following logic:

To calculate dp[i], we will check if i is divisible by 2 or 3. If i is divisible by 2 or 3, we can reduce it to i/2 or i/3 in less number of operations. Therefore, we will take the minimum of dp[i/2]+1 and dp[i/3]+1.

If i is not divisible by 2 or 3, then we can directly subtract 1 from i and get i-1. Therefore, dp[i] will be minimum of dp[i-1]+1 and the value calculated in the previous step (i.e., minimum of dp[i/2]+1 and dp[i/3]+1).

Finally, we will return dp[n].

Time Complexity Analysis:

For each i, at most 3 states can be reached, i-1, i/2 and i/3. Therefore, the time complexity of the above algorithm is O(n). The space complexity is also O(n) due to the use of array dp[n+1].

Python Code:

def minOperations(n: int) -> int: dp = [0]*(n+1) for i in range(2, n+1): if i%2 == 0: dp[i] = min(dp[i//2]+1, dp[i-1]+1) elif i%3 == 0: dp[i] = min(dp[i//3]+1, dp[i-1]+1) else: dp[i] = dp[i-1]+1 return dp[n]

#Sample Input n = 10

#Sample Output print(minOperations(n)) #3

1