Optimal Division - Leetcode Solution

Problem:

You are given an integer array nums. The adjacent integers in nums will perform the float division.

For example, for nums = [2,3,4], we will evaluate the expression "2/3/4".

However, you can add any number of parenthesis at any position to change the priority of operations. You want to add these parentheses such that the value of the expression after the evaluation is maximum.

Return the corresponding expression that has the maximum value in string format. You can return any valid expression.

Example 1:

Input: nums = [1000,100,10,2] Output: "1000/(100/10/2)" Explanation: 100/10/2 = 5 1000/5 = 200

Example 2:

Input: nums = [2,3,4] Output: "2/(3/4)" Explanation: 2/3/4 = 0.166666667 2/(3/4) = 2.66666667

Example 3:

Input: nums = [3,2] Output: "3/2" Explanation: 3/2 = 1.5

Constraints:

2 <= nums.length <= 10^4 1 <= nums[i] <= 1000 Answers within 10^-4 of the actual value will be accepted as correct.

Solution:

The problem is asking us to add parenthesis in the given expression so as to get the maximum possible answer. As we can add any number of parenthesis, we should try to maximize the expression as much as possible. We should always divide the bigger numbers than the smaller ones because only then we will get the maximum value of the expression.

Algorithm:

1. First, we will check if there are only two numbers in the array, then simply divide the first number by the second number and return the string expression like "a/b".
2. If the array contains more than two numbers, then take variables "a" and "b" and initialize them with the first two numbers in the array. Then, loop through the remaining numbers in the array, divide "a" by "b", and store the result in "a" and store the next element in "b". Now, keep doing this operation until we reach the end of the array.
3. By doing this, we will get the result of the expression without adding any parenthesis. But it may not be the maximum value we can get. So we will try to add parenthesis to maximize the value.
4. Now, loop through the array starting from the third element (as we already took first two numbers in step 2). At each iteration, calculate the value of the expression so far by dividing first i elements of the array and then dividing the remaining elements. Add parenthesis around the remaining elements to get the maximum value.
5. Return the resulting string expression with maximum value.

Implementation:

Here's the Python implementation for the above algorithm:

class Solution: def optimalDivision(self, nums: List[int]) -> str: n = len(nums) if n == 1: return str(nums[0]) if n == 2: return str(nums[0]) + "/" + str(nums[1])

    a = nums[0]
    b = nums[1]
    result = str(a) + "/(" + str(b)
    
    for i in range(2, n):
        result += "/" + str(nums[i])
        b = nums[i]
    
    result += ")"
    
    return result

1