Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

The title

Given a set of positive integers, floating point division will be performed between adjacent integers. For example, [2,3,4] -> 2/3/4.

However, you can change the priority of the arithmetic by adding as many parentheses as you like in any place. You need to figure out how to add parentheses to get the maximum result and return the corresponding expression in string format. Your expressions should not contain redundant parentheses.

Example:

Input: [1000,100,10,2] Output: "1000/(100/10/2)" 1000/(100/10/2) = 1000/((100/10)/2) = 200 However, the following bold parentheses "1000/((100/10)/2)" are redundant because they do not affect the priority of the operation, so you need to return "1000/(100/10/2)".  Other use cases: 1000/(100/10)/2 = 50 1000/(100/(10/2)) = 50 1000/100/10/2 = 0.5 1000/100/(10/2) = 2Copy the code

Description:

  1. The length of the input array is between [1, 10].
  2. Each element in the array is between [2, 1000] in size.
  3. There is only one optimal division solution per test case.

thinking

This is an interesting problem of medium difficulty.

As we can see from the problem, there is only one operator, division, and the numbers are all positive integers. The only thing we can do is put any number of parentheses in any number of places, do different things, get different results, get the maximum number of results.

Considering the characteristics of division operation, when both the divisor and dividend are positive integers, the larger the dividend and the smaller the divisor, the larger the result will be. Then the problem is solved! We only need nums[0] as the dividend and the result of the rest of the numbers as the divisor.

answer

Method 1: Math

To maximize the fraction x/y, make the numerator x as large as possible and the denominator y as small as possible. Since every element in the array nums is greater than 1, when x = nums[0], y = nums[1] / nums[2] /… / nums[n-1] is the minimum value.

var optimalDivision = function(nums) { const n = nums.length if (n === 1) { return '' + nums[0] } if (n === 2) { return '' + nums[0] + "/" + '' + nums[1] } let res = '' for (let i = 1; i < n; i++) { if (i ! == n - 1) { res += `${nums[i]}/` } else { res += `${nums[i]}` } } return `${nums[0]}/(${res})` }Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the length of the string num, and the array is traversed only once.
  • Space complexity: O(1). No additional storage is required except for the function return value.

reference

  • The optimal division