Easy to understand simple O(n) solution with explanation


  • 40
    I

    X1/X2/X3/../Xn will always be equal to (X1/X2) * Y, no matter how you place parentheses. i.e no matter how you place parentheses, X1 always goes to the numerator and X2 always goes to the denominator. Hence you just need to maximize Y. And Y is maximized when it is equal to X3 *..*Xn. So the answer is always X1/(X2/X3/../Xn) = (X1 *X3 *..*Xn)/X2

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

  • 1

    Smart move. I thought it should use Dynamic Programing but it turned out not.


  • 4
    A

    @Mr.Bin
    I thought it's similar to Matrix-chain multiplication in CLRS, so I also use DP, which takes O(n^3) and is hard to construct final expression. Very bad idea to use DP.

    class Solution(object):
        def optimalDivision(self, nums):
            """
            :type nums: List[int]
            :rtype: str
            """
            n = len(nums)
            min_dp = [[1001.0] * n for i in xrange(n)]
            max_dp = [[0.0] * n for i in xrange(n)]
            min_k = [[None] * n for i in xrange(n)]
            max_k = [[None] * n for i in xrange(n)]
            for i, num in enumerate(nums):
                min_dp[i][i] = float(num)
                max_dp[i][i] = float(num)
            for l in xrange(2, n + 1):
                for i in xrange(n - l + 1):
                    j = i + l - 1
                    for k in xrange(i, j):
                        if min_dp[i][k] / max_dp[k + 1][j] < min_dp[i][j]:
                            min_dp[i][j] = min_dp[i][k] / max_dp[k + 1][j]
                            min_k[i][j] = k
                        if max_dp[i][k] / min_dp[k + 1][j] > max_dp[i][j]:
                            max_dp[i][j] = max_dp[i][k] / min_dp[k + 1][j]
                            max_k[i][j] = k
            return self.helper(0, max_k[0][n-1], n - 1, min_k, max_k, nums, 1)
    
        def helper(self, i, k, j, min_k, max_k, nums, flag):
            if i == j:
                return str(nums[i])
            if flag:
                s1 = self.helper(i, max_k[i][k], k, min_k, max_k, nums, 1)
                s2 = self.helper(k + 1, min_k[k + 1][j], j, min_k, max_k, nums, 0)
            else:
                s1 = self.helper(i, min_k[i][k], k, min_k, max_k, nums, 0)
                s2 = self.helper(k + 1, max_k[k + 1][j], j, min_k, max_k, nums, 1)
            if k + 1 != j:
                s2 = '(' + s2 + ')'
            return s1 + '/' + s2

  • 3

    Yeah, yeah. I thught it too. And it took all rest time on this problem. It's very hard to back track the required expression using DP.

    Thanks for your posting.


  • 2
    F

    This problem seems strange. As you said, if the input is [x0, x1, ....], x0 will always be numerator, so we should make the denominator as small as possible to get the maximum result.
    Since all the numbers are positive integer, it is clear that x1/x2/../xn results in the smallest denominator.

    To be more concise:

    function optimalDivision (nums) {
        var N = nums.length;
        if(N <= 2) return nums.join('/');
        return nums[0] + '/' + '(' + nums.slice(1).join('/') + ')';
    }
    

  • 6
    C

    I think this is not a programming question, it's more about formulation and math tricks. Nice answer but bad question


  • 1
    G

    Java version like this:

    public class Solution {
        public String optimalDivision(int[] nums) {
            String ret = "";
            if (nums.length == 0) {
                return ret;
            }
            if (nums.length == 1) {
                ret = Integer.toString(nums[0]);
                return ret;
            }
            if (nums.length == 2) {
                ret = Integer.toString(nums[0]) + "/" + Integer.toString(nums[1]);
                return ret;
            }
            
            ret = Integer.toString(nums[0]) + "/(" + Integer.toString(nums[1]);
            for (int i=2; i<nums.length; i++) {
                ret += "/" + Integer.toString(nums[i]);
            }
            ret += ")";
            return ret;
        }
    }
    

  • 0

    @i9r0k said in Easy to understand simple O(n) solution with explanation:

    So the answer is always X1/(X2/X3/../Xn) = (X1 *X3 *..*Xn)/X2

    However, the output is "1000/(100/10/2)" to the given input [1000,100,10,2]. But as per my understanding of your explanation, it should be (1000*10*2)/100. So, could you please elaborate?


  • 0
    I

    @BatCoder It gives the same result. 1000/(100/10/2) = (1000 *10 *2)/100 = 200. But per problem statement the fraction can not be simplified and 1000/(100/10/2) is the only acceptable form of answer.


  • 0

    @i9r0k Got your point. Thank you! :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.