Divide and conquer problem

def multiply_optimized(poly1, poly2):
t1=split(poly1, poly2)
a0=t1[0][0]
a1=t1[0][1]
b0=t1[1][0]
b1=t1[1][1]

a1=increase_exponent(a1,len(a0))
b1=increase_exponent(b1,len(b0))

#print(f'a1:{a1},b1:{b1}')
result = []
y= multiply_basic(add(a0,a1),add(b0,b1))
z=multiply_basic(a1,b1)
u=multiply_basic(a0,b0)
u_add_z= add(u,z)
y_sub_u_add_z=sub(y,u_add_z)
result = add(u,y_sub_u_add_z)
result = add(result,z)


return result

this is my code for divide and conquer problem all the test cases are passed except #test 9 and #test21

1 Like

code for subratication
def sub(poly1,poly2):
result = [0]*max(len(poly1),len(poly2))
for i in range(len(result)):
if i < len(poly1):
result[i] = poly1[i]
if i < len(poly2):
result[i] -= poly2[i]
return result

code for add
def add(poly1, poly2):
“”“Add two polynomials”""
result = [0] * max(len(poly1), len(poly2))
for i in range(len(result)):
if i < len(poly1):
result[i] += poly1[i]
if i < len(poly2):
result[i] += poly2[i]
return result

code for split
def split(poly1, poly2):
“”“Split each polynomial into two smaller polynomials”""
mid = max(len(poly1), len(poly2)) // 2
return (poly1[:mid], poly1[mid:]), (poly2[:mid], poly2[mid:])

code for increase exponential
def increase_exponent(poly, n):
“”“Multiply poly1 by x^n”""
return [0] * n + poly

You don’t have the condition to handle the case where poly1 or poly2 is empty,
And there is no base case to resolve the function.

Also,

You are not doing recursion here, you are just calling another function (multply_basic), here.

You are just using the multiply_basic function but with a lot more extra steps.
For it to be recursion you need to call the same function i.e. multiply_optimized inside the multiply_optimized function.

def multiply_optimized(poly1, poly2):
result = []
if len(poly1)==0 and len(poly2)==0:
return result
if len(poly1)==0:
poly1=[1]
elif len(poly2)==0:
poly2=[1]
t1=split(poly1, poly2)
a0=t1[0][0]
a1=t1[0][1]
b0=t1[1][0]
b1=t1[1][1]

a1=increase_exponent(a1,len(a0))
b1=increase_exponent(b1,len(b0))

#print(f'a1:{a1},b1:{b1}')
y= multiply_basic(add(a0,a1),add(b0,b1))
z=multiply_basic(a1,b1)
u=multiply_basic(a0,b0)
u_add_z= add(u,z)
y_sub_u_add_z=sub(y,u_add_z)
result = add(u,y_sub_u_add_z)
result = add(result,z)


return result

i have resolved the case to handle the if poly1 or poly2 is empty is this correct and i 'm not getting the point how to resolve the base case of the function
You are not doing recursion here, you are just calling another function (multply_basic), here.

You are just using the multiply_basic function but with a lot more extra steps.
For it to be recursion you need to call the same function i.e. multiply_optimized inside the multiply_optimized function
n you make this more clear for me plz…

All the test case are solved only test case 9 && 21 are showing failed do you know what is the sample input and output of those test case

No one knows what the inputs are. That’s the point - make an algorithm which will work for every possible correct case.

1 Like

Ok, considering you are at the multiply_optimized function, I’m assuming that you have already done and cleared all test cases for the multiply_basic function.

So, you have a properly working multiply_basic function that multiplies list poly1 and poly2 but you find it’s a bit inefficient for the worst case.
Therefore, to overcome the inefficiency you are using Divide and Conquer.

In Divide and Conquer,

  1. We divide the problem into smaller sub-problem
  2. Conquer those subproblems using recursion. if they are small enough, use the base case.
  3. Combine the solution to the subproblems into the solution to the main problem.

An example of recursion:

  #This is a recursive function
  #To find the factorial of an integer

def fact(x):

    if x == 1:           # Base Case when the subproblem is x==1
        return 1
    else:
        return (x * fact(x-1))  #Breaking the problem into subproblem and using recursion

   # fact(x-1) calls the function fact(x) inside the fact(x) function.

What I meant here is,

That you are not breaking the problem into subproblems recursively.
You are just breaking the problem 1 time and then using the multiply_basic function, which was already able to solve the whole problem.

In simpler words, try making the multiply_optimized function without the mutliply_basic function.

Also, First, try to solve the problem with recursion or divide and conquer
And then try evaluating the test cases.