Divide and Conquer, Time Limit Exceeded.


  • 0
    X

    Here is my Divide and Conquer solution in python, but time limit exceeded unfortunately.

    class Solution_2(object):
        def multiply(self, num1, num2):
            m, n = len(num1), len(num2)
            max_len = max(m, n)
            num1 = '0' * (max_len - m) + num1
            num2 = '0' * (max_len - n) + num2
            if max_len <= 1:
                return str(int(num1) * int(num2))
    
            # Divide and conquer.
            m1, m2 = num1[:max_len / 2], num1[max_len / 2:]
            n1, n2 = num2[:max_len / 2], num2[max_len / 2:]
            m1_n1 = self.multiply(m1, n1) + "0" * (max_len - max_len / 2) * 2
            m1_n2 = self.multiply(m1, n2) + "0" * (max_len - max_len / 2)
            m2_n1 = self.multiply(m2, n1) + "0" * (max_len - max_len / 2)
            m2_n2 = self.multiply(m2, n2)
    
            product = self.add(m1_n1, self.add(m1_n2, self.add(m2_n1, m2_n2)))
            first_not_0 = 0
            while first_not_0 < len(product) and product[first_not_0] == '0':
                first_not_0 += 1
            return product[first_not_0:] or "0"
    
        def add(self, num1, num2):
            carry_in = 0
            max_len = max(len(num1), len(num2))
            add_sum = [0] * (max_len)
            for i in range(-1, -1 - max_len, -1):
                pos_1 = int(num1[i]) if i >= -len(num1) else 0
                pos_2 = int(num2[i]) if i >= -len(num2) else 0
                add_sum[i] = (pos_1 + pos_2 + carry_in) % 10
                carry_in = (pos_1 + pos_2 + carry_in) / 10
    
            if carry_in:
                add_sum.insert(0, carry_in)
    
            return "".join(map(str, add_sum))

Log in to reply
 

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