Table of Contents

# Optimal Division – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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 the value of the expression after the evaluation is maximum.

Return *the corresponding expression that has the maximum value in string format*.

**Note:** your expression should not contain redundant parenthesis.

**Example 1:**

Input:nums = [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 do not 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

**Example 2:**

Input:nums = [2,3,4]Output:"2/(3/4)"Explanation:(2/(3/4)) = 8/3 = 2.667 It can be shown that after trying all possibilities, we cannot get an expression with evaluation greater than 2.667

**Constraints:**

`1 <= nums.length <= 10`

`2 <= nums[i] <= 1000`

- There is only one optimal division for the given input.

# C++ Optimal DivisionLeetCode Solution

```
``````
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
string expr;
for (int i = 0; i < n; i++) {
if (i > 0) {
expr += "/";
}
if (i == 1 && n > 2) {
expr += "(";
}
expr += to_string(nums[i]);
if (i == n - 1 && n > 2) {
expr += ")";
}
}
return expr;
}
};
```

# Java Optimal Division LeetCode Solution

```
``````
public class Solution {
class Result {
String str;
double val;
}
public String optimalDivision(int[] nums) {
int len = nums.length;
return getMax(nums, 0, len - 1).str;
}
private Result getMax(int[] nums, int start, int end) {
Result r = new Result();
r.val = -1.0;
if (start == end) {
r.str = nums[start] + "";
r.val = (double)nums[start];
}
else if (start + 1 == end) {
r.str = nums[start] + "/" + nums[end];
r.val = (double)nums[start] / (double)nums[end];
}
else {
for (int i = start; i < end; i++) {
Result r1 = getMax(nums, start, i);
Result r2 = getMin(nums, i + 1, end);
if (r1.val / r2.val > r.val) {
r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
r.val = r1.val / r2.val;
}
}
}
//System.out.println("getMax " + start + " " + end + "->" + r.str + ":" + r.val);
return r;
}
private Result getMin(int[] nums, int start, int end) {
Result r = new Result();
r.val = Double.MAX_VALUE;
if (start == end) {
r.str = nums[start] + "";
r.val = (double)nums[start];
}
else if (start + 1 == end) {
r.str = nums[start] + "/" + nums[end];
r.val = (double)nums[start] / (double)nums[end];
}
else {
for (int i = start; i < end; i++) {
Result r1 = getMin(nums, start, i);
Result r2 = getMax(nums, i + 1, end);
if (r1.val / r2.val < r.val) {
r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
r.val = r1.val / r2.val;
}
}
}
//System.out.println("getMin " + start + " " + end + "->" + r.str + ":" + r.val);
return r;
}
}
```

# Python 3 Optimal Division LeetCode Solution

```
``````
def optimalDivision(self, A):
A = map(str, A)
if len(A) <= 2: return '/'.join(A)
return '{}/({})'.format(A[0], '/'.join(A[1:]))
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1