> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/maths/optimal-division.md).

# Optimal Division

Given a list of **positive integers**, the adjacent integers will perform the float division. For example, \[2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the **maximum** result, and return the corresponding expression in string format. **Your expression should NOT contain redundant parenthesis.**

**Example:**<br>

```
Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
since they don't influence the operation priority. So you should return "1000/(100/10/2)". 

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
```

**Note:**

1. The length of the input array is \[1, 10].
2. Elements in the given array will be in range \[2, 1000].
3. There is only one optimal division for each test case.

```java
class Solution {
    // The dafault flow is 1st/2nd/3rd...
    // Now the first number will always be in numerator
    // And the 2nd number will always be in denominator
    // Now we need to reduce denominator for max ans
    // So if we place only 1 pair of brackets as shown in example
    // All the numbers 3,4... will go into numerator(because of the default flow)
    public String optimalDivision(int[] nums) {
        StringBuilder ans = new StringBuilder();
        if (nums.length == 1)
            return Integer.toString(nums[0]);
        else if (nums.length == 2)
            return Integer.toString(nums[0]) + "/" + Integer.toString(nums[1]);
        for (int i = 0; i < nums.length; i++) {
            String n = Integer.toString(nums[i]);
            if (i == 0)
                ans.append(n + "/(");
            else if (i != nums.length - 1)
                ans.append(n + "/");
            else
                ans.append(n + ")");
        }
        return ans.toString();
    }
}
```