Related studies: Here Problem Link Problem description: The laboratory of Microbiology department has been attacked by several robbers recently. They robbed and stole many valuable samples of viruses, bacteria, microorganisms. While being in hurry, they broke a tube. The tube contained sample of one of the most dangerous germs called Dangerm. The tube contained exactly
Category: DP
Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]
Problem: Given two integers ‘n’ and ‘sum’, find count of all n digit numbers with sum of digits as ‘sum’. Leading 0’s are not counted as digits. Print your output % 10^9+7.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <stdio.h> #define MOD 1000000007 unsigned long long dp[101][1001]; unsigned long long Count(int n,int sum) { int i; if(n==0) { if(sum==0) return 1; return 0; } if(dp[n][sum]!=-1) return dp[n][sum]; unsigned long long res=0; for(i=0;i<=9;i++) { if(sum-i>=0) res = (res+Count(n-1,sum-i))%MOD; } return dp[n][sum]=res; } unsigned long long countDigit(int n,int sum) { int i; if(n==0) { if(sum==0) return 1; return 0; } unsigned long long res=0; for(i=1;i<=9;i++) { if(sum-i>=0) res = (res+Count(n-1,sum-i))%MOD; } return res; } int main() { //code int t,n,sum,i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&sum); for(i=0;i<=n;i++) { for(j=0;j<=sum;j++) dp[i][j]=-1; } int d = countDigit(n,sum); if(d==0) d=-1; printf("%d\n",d); } return 0; } |
Word Break [ IBM – Google ]
Problem: Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details. Consider the following dictionary { i, like, sam, sung, samsung, mobile, ice,cream, icecream, man, go, mango} Input: ilike Output: Yes The string can be
Edit Distance of Two Given String [ Amazon ]
Problem:Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′. a.Insert b.Remove c.Replace All of the above operations are of cost=1.Both the strings are of lowercase. Hint: Use DP to solve the problem. This problema also can be solved using
Continue Reading “Edit Distance of Two Given String [ Amazon ]”
Find K-Palindrome of a string [ Amazon]
Problem:A string is k pallindrome if it can be transformed into a palindrome on removing at most k characters from it. Link
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/*You are required to complete this function*/ bool is_k_pallin(string s,int k) { //Your code here string rev_s=""; int n = s.size(); for(int i=s.size()-1;i>=0;i--) rev_s.append(1u,s[i]); int dp[n+1][n+1]; for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(i==0) dp[i][j]=j; else if(j==0) dp[i][j]=i; else if(s[i-1]==rev_s[j-1]) dp[i][j]=dp[i-1][j-1]; else if(s[i-1]!=rev_s[j-1]) dp[i][j] = 1+ (dp[i-1][j]<dp[i][j-1]?dp[i-1][j]:dp[i][j-1]); } } if(dp[n][n]<=2*k) return 1; return 0; } |