Division Evaluation

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Amazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3
4 5 6
4
20 5 30 2
Sample Output 1:
4/(5/6)
20/(5/30/2)
For Example:
For the first test case, ‘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.

For the second test case, ‘arr’ = [20, 5, 30, 2], Here the possible expressions are ‘20/5/30/2’, ‘20/(5/30/2)’, ‘20/(5/30)/2’, 20/(5/(30/2))’, ‘20/((5/30)/2)’ and ‘20/5/(30/2)’ whose values are 1.667, 240, 60, 0.333 and 0.267 respectively, therefore ‘20/(5/30/2)’ is the answer.
Sample Input 2:
2
1
5
2
40 4
Sample Output 2:
5
40/4
Hint

Try all the possible combinations.

Approaches (2)
Brute Force

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.
Time Complexity

O(N!), Where N is the size of the array

 

We are iterating through all the permutations of adding the parentheses in the expression. The total number of permutations turned out to be O(N!).

Space Complexity

O(N^2), Where N is the size of the array

 

The recursion stack will take up O(N) space, and the for each recursive permutation we are creating a string of maximum length O(N). Hence the overall space complexity is O(N)*O(N) = O(N^2).

Code Solution
(100% EXP penalty)
Division Evaluation
Full screen
Console