Python is an interpreted high-level general-purpose programming language.
PROBLEM 1:
Problem statement
Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each
of S = { S1, S2, .. , SM } valued coins.
Input Format
First line of input contains two space separate intergers N and M where N represents the N cents and
M represents the number of denominations of different coins.
Next line of input contains M integers - the denominations of different coins.
Constraints
1 <= N,M <= 10^3
Output Format
Print the number of ways to make change for N cents.
PYTHON SOLUTION:
def count(S, m, n ):
if (n == 0):
return 1
if (n < 0):
return 0;
if (m <=0 and n >= 1):
return 0
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
n,m=map(int,input().split())
arr = list(map(int,input().split()))
print(count(arr, m, n))
PROBLEM 2:
Problem statements
Given a string s, find length of the longest prefix which is also suffix. The prefix and suffix should not be
overlap
Input Format
A string s.
Constraints
1<=|s|<=10^5
Output Format
Output as per specified in problem statement.
PYTHON SOLUTION:
def longestPrefixSuffix(s) :
n = len(s)
for res in range(n // 2, 0, -1) :
prefix = s[0: res]
suffix = s[n - res: n]
if (prefix == suffix) :
return res
return 0
if __name__ == "__main__":
s = input().strip()
print(longestPrefixSuffix(s))
PROBLEM 3:
Problem statement
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The
efficient way is the one that involves the least number of multiplications.
The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices +
1) where the ith matrix has the dimensions (arri-1 x arri).
Input Format
First line of input contains N-the size of the array. Next line of input contains N integers the N elements
of the array.
Constraints
2 ≤ N ≤ 100
1 ≤ arri ≤ 500
Output Format
Print the number of operations involved in the most efficient way if matrix chain multiplication.
PYTHON SOLUTION:
import sys
def MatrixChainOrder(p, i, j):
if i == j:
return 0
_min = sys.maxsize
for k in range(i, j):
count = (MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i-1] * p[k] * p[j])
if count < _min:
_min = count
return _min
n=int(input())
arr = list(map(int,input().split()))
print(MatrixChainOrder(arr, 1, n-1))
Post a Comment