Dividing Sequence

Write an expression for Best(i) in terms of Best(j) with j<i, with base case Best(1) = 1. Solve this recurrence using dynamic programming.


l=[]
s=input()
s=int(s)
st=[]
for y in range(s):
    l.append(int(input()))
    st.append(0)
def best(k):
    st[0]=1
    for i in range(0,len(l)):
        m=1
        for j in range(0,i):
            if(k[i]%k[j]==0):
                m=max(m,st[j]+1)
        st[i]=m
best(l)

print (max(st))

Add And Multiply Polynomials

Write Python functions for the following operations:

  addpoly(p1,p2) multpoly(p1,p2)
that add and multiply two polynomials, respectively.
You may assume that the inputs to these functions follow the representation given above.  Correspondingly, the outputs from these functions should also obey the same constraints.


def addpoly(p1,p2):
o=[]
if(len(p1)>len(p2)):
  h1=p2
  h2=p1
else:
  h1=p1
  h2=p2
for x in h1:
f=0
for y in h2:
if(x[1]==y[1]):
k=(y[0]+x[0],y[1])
f=1
break
if(f==0):
h2.append(x)


return h2[1:]

def multpoly(p1,p2):
l=[]
p=[]
if len(p1)>len(p2):
h2=p1
h1=p2
else:
h2=p2
h1=p1
for x in h1:
for y in h2:
k=(x[0]*y[0],y[1]+x[1])
l=add(l,k)

return l

Orangecap IPL

Define a Python function "orangecap(d)" that reads a dictionary d of this form and identifies the player with the highest total score.  Your function should return a pair (playername,topscore) where playername is a string, the name of the player with the highest score, and topscore is an integer, the total score of playername.



def orangecap(d):
    d2={}
    for p in d:
        for q in d[p]:
            d2[q] = d2.get(q, 0) + d[p][q]
    name = max(d2, key=d2.get)

    return name, d2[name]

List Alternating Values

Define a Python function "alternating(l)" that returns True if the values in the input list alternately go up and down (in a strict manner).


def alternating(l):
if(len(l)>1):
if(l[0]>l[1]):
for i in range(len(l)-1):
if(l[i]==l[i-1]):
return False
if(i%2==0):
if(l[i]<l[i+1]):
return False
if(l[0]<l[1]):
for i in range(len(l)-1):
if(i%2==0):
if(l[i]>l[i+1]):
return False

return True

Matrix Multiplication

Write a Python function "matmult(m1,m2)" that takes as input two matrices using this row-wise representation and returns the matrix product m1*m2 using the same representation.
You may assume that the input matrices are well-formed and have compatible dimensions.



def matmult(m1,m2):
    C = [[0 for row in range(len(m1))] for col in range(len(m2[0]))]
    for i in range(len(m1)):
        for j in range(len(m2[0])):
            for k in range(len(m2)):
                C[i][j] += m1[i][k]*m2[k][j]

    return C

Order of Descending

Define a Python function "descending(l)" that returns True if each element in its input list is at most as big as the one before it


def descending(l):
for i in range(0,len(l)-1):
if(l[i]<l[i+1]):
return False

return True

Sum Of Prime

Write a function sumprimes(l) that takes as input a list of integers and retuns the sum of all the prime numbers in l.


def sumprimes(l):
    sum=0
    for i in range(len(l)):
      if l[i]>0:
        j=i
        flag=0
        for k in range(2,l[i]):
            if l[j]%k==0:
                flag=1
                break
        if flag==0:
           sum=sum+l[j]

    return sum

Bracket Match

Write a function matched(s) that takes as input a string s and checks if the brackets "(" and ")" in s are matched: that is, every "(" has a matching ")" after it and every ")" has a matching "(" before it.  Your function should ignore all other symbols that appear in s.  Your function should return True if s has matched brackets and False if it does not.


def matched(s):
    op=0
    for i in range(len(s)):
        if s[i]==")":
            if op==0:
                return False
            else:
                op=op-1
        elif s[i]=="(":
            op=op+1
    if(op==0):
        return True
    else:
        return False
 

Reverse Integer

Write a function that takes as input a positive integer n and returns the integer obtained by reversing the digits in n.


def intreverse(n):
  rev=0
  while(n>0):
    d=n%10
    rev=(rev*10)+d
    n=n//10
  return rev