Last Updated: 26 Nov, 2021
Division Evaluation
Moderate
Asked in company
You are given an array of integers, your task is to perform float division among adjacent numbers in the array. You can add any number of parentheses at any position in the array. You have to add the parentheses in such a way that it maximizes the value of the evaluation and return the expression with the parentheses.
Note:
You should return expressions without redundant parentheses, i.e if the returning expression is ‘(a/b)/c’, you should return ‘a/b/c’.
For example:
You are given ‘arr’ = [4, 5, 6], Here the possible expressions are ‘4/5/6’, ‘4/(5/ 6)’, whose values are 0.133 and 4.81 respectively, therefore ‘4/(5/6)’ is the answer.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing the size of the array.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format:
For each test case print the string that represents the expression with the maximum value.
Constraints:
1 <= T <= 10
1 <= N <= 10^6
1 <= arr[i] <= 10^9
Time Limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we will try to put the parentheses at every position, so we will divide ‘arr’ array into two parts left and right, both returning their maximum as well as minimum values.
Now If we divide a large number by a smaller number it will give a larger answer.
So to find the solution to an array, divide the maximum of the left side to the minimum for the right side. Divide the array at every possible position and get the maximum possible answer for the array.
To do this we create a class Value, which stores maximum and minimum values in integer and as a string of any subarray.
We also create a recursive function getMaxValue(arr, start, end), to get the Value Object from the subarray of ‘arr’, ‘arr[start: end]’
Algorithm:
- In the getMaxValue(arr, start, end) function
- Create a new Value object val
- If start is equal to end
- Set val.maxVal and val.minVal as arr[start]
- Set val.maxStr and val.minStr as arr[start] converted to string
- Return val
- Set val.minVal and val.maxVal as positive and negative infinity respectively.
- Set val.maxStr and val.minStr as empty string.
- Iterate i from start to end - 1
- leftVal as getMaxValue(arr, start, i)
- rightVal as getMaxValue(arr, i + 1, end)
- If val.minVal is greater than leftVal.minVal / rightVal.maxVal
- Set val.minVal as leftVal.minVal / rightVal.maxVal
- Set val.minStr as leftVal.minStr + “/”
- Add “(” to val.minStr if i+1 is equal to end
- Add rightVal.maxStr to val.minStr
- Add “)” if i + 1 is equal to end.
- If val.maxVal is less than leftVal.maxVal / rightVal.minVal
- Set val.maxVal as leftVal.maxVal / rightVal.minVal
- Set val.maxStr as leftVal.minStr + “/”
- Add “(” to val.maxStr if i+1 is equal to end
- Add rightVal.minStr to val.maxStr
- Add “)” if i + 1 is equal to end.
- Return val
- In the main function
- Set val as getMaxValue(arr, 0, size of ‘arr’ - 1)
- Return val.maxStr.
In this approach, we will make a simple observation, like the last approach, that if we divide a large number by a smaller number it will give a larger answer.
Therefore we can simply evaluate the expression from the second number to the last and divide the first number by the result of the expression from 2nd number to the last number.
Algorithm:
- Set n as the size of the array ‘arr’
- If n is equal to 1, convert arr[0] to string and return
- If n is equal to 2, convert arr[0] and arr[1] to string, concatenate them with a ‘/’ and return
- Set exp as arr[0] converted to a string and concatenate a ‘/(‘ to exp.
- Iterate i from 1 to n - 2:
- Convert arr[i] to string and concatenate to exp.
- Concatenate a ‘/’ to exp
- Convert arr[n - 1] to string and concatenate it to exp
- Concatenate a ‘)’ to exp
- Return exp