2016 – Live with passion

Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]

Asif NaeemOctober 2, 2016

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.

#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;
}

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;

}

Steins GCD Algorithm

Asif NaeemSeptember 28, 2016

Algorithm to find GCD using Stein’s algorithm gcd(a,b) If both and b are 0, gcd is zero gcd(0, 0) = 0. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2

Continue Reading “Steins GCD Algorithm” →

Word Break [ IBM – Google ]

Asif NaeemSeptember 25, 2016

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

Continue Reading “Word Break [ IBM – Google ]” →

Almost Prime number

Asif NaeemSeptember 24, 2016

Problem:A no is said to be k-Almost Prime Number if it has exactly k prime factors (not necessary distinct). Your task is to complete the functionprintKAlmostPrimes which takes two argument k and N and prints the first N numbers that are k prime. Problem Link

/*You are required to complete this function*/

bool isPrime(int n)
{
    bool arr[20];
    int i;
    arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1;
    arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1;
    
    if(n<20)
    {
        if(arr[n]==1)
        return 1;
        else if(arr[n]==0)
        return 0;
    }
    if(n%2==0)
    return 0;
    for(i=3;i<=sqrt(n);i+=2)
    {
        if(n%i==0)
        return 0;
    }
    return 1;
}
int CountOfPrime(int n)
{
    int cnt=0,i;
    while(n%2==0)
    {
        cnt+=1;
        n/=2;
    }
    for(i=3;i<=sqrt(n);i+=2)
    {
        if(isPrime(i)==0)
        continue;
        while(n%i==0)
        {
            cnt+=1;
            n/=i;
        }
    }
    if(n>2)
    cnt+=1;
    return cnt;
}
void printKAlmostPrimes(int k, int n)
{
//Your code here
    int i,num;
    for(i=1,num=2;i<=n;num++)
    {
        if(CountOfPrime(num)==k)
        {
            printf("%d ",num);
            i++;
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

/*You are required to complete this function*/

bool isPrime(int n)

{

bool arr[20];

int i;

arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1;

arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1;

if(n<20)

{

if(arr[n]==1)

return 1;

else if(arr[n]==0)

return 0;

}

if(n%2==0)

return 0;

for(i=3;i<=sqrt(n);i+=2)

{

if(n%i==0)

return 0;

}

return 1;

}

int CountOfPrime(int n)

{

int cnt=0,i;

while(n%2==0)

{

cnt+=1;

n/=2;

}

for(i=3;i<=sqrt(n);i+=2)

{

if(isPrime(i)==0)

continue;

while(n%i==0)

{

cnt+=1;

n/=i;

}

if(n>2)

cnt+=1;

return cnt;

}

void printKAlmostPrimes(int k, int n)

{

//Your code here

int i,num;

for(i=1,num=2;i<=n;num++)

{

if(CountOfPrime(num)==k)

{

printf("%d ",num);

i++;

}

Jumping Numbers [ Google – Microsoft – Amazon ]

Asif NaeemAugust 29, 2016

Problem:Given a positive number x, print all Jumping Numbers smaller than or equal to x. A number is called as a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and

Continue Reading “Jumping Numbers [ Google – Microsoft – Amazon ]” →

Edit Distance of Two Given String [ Amazon ]

Asif NaeemAugust 28, 2016

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]

Asif NaeemAugust 28, 2016

Problem:A string is k pallindrome if it can be transformed into a palindrome on removing at most k characters from it. Link

/*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;
}

/*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;

}

Kadane’s Algorithm [ Macrosoft – Amazon – FlipKart ]

Asif NaeemAugust 27, 2016

Problem: Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum. Link

#include <stdio.h>

int main() {
	//code
	int t,n,i,a;
	int mx_end_here,mx_so_far;
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d",&n);
	    mx_end_here=0,mx_so_far=-1000;
	    for(i=0;i<n;i++)
	    {
	        scanf("%d",&a);
	        if(a<0)
	        {
	            if(mx_so_far<a)
	            mx_so_far=a;
	            mx_end_here=mx_end_here+a;
	            if(mx_end_here<0)
	            mx_end_here=0;
	        }
	        else if(a>=0)
	        {
	            mx_end_here=mx_end_here+a;
	            if(mx_end_here>mx_so_far)
	            mx_so_far=mx_end_here;
	        }
	    }
	    printf("%d\n",mx_so_far);
	}
	return 0;
}

#include <stdio.h>

int main() {

//code

int t,n,i,a;

int mx_end_here,mx_so_far;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

mx_end_here=0,mx_so_far=-1000;

for(i=0;i<n;i++)

{

scanf("%d",&a);

if(a<0)

{

if(mx_so_far<a)

mx_so_far=a;

mx_end_here=mx_end_here+a;

if(mx_end_here<0)

mx_end_here=0;

}

else if(a>=0)

{

mx_end_here=mx_end_here+a;

if(mx_end_here>mx_so_far)

mx_so_far=mx_end_here;

}

printf("%d\n",mx_so_far);

}

return 0;

}

Maximum Product Sub array [ Microsoft – Amazon ]

Asif NaeemAugust 27, 2016

Problem : Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Link Discussion: It is a Similiar problem to maximum sum sub array problem. Notice,maximum product can also be obtained by minimum (negative) product ending with the last element multiplied by this element. we use mn_end_here(can be

Continue Reading “Maximum Product Sub array [ Microsoft – Amazon ]” →

Year: 2016

Count of n digit numbers whose sum of digits equals to given sum [ Amazon ]

Steins GCD Algorithm

Word Break [ IBM – Google ]

Almost Prime number

Jumping Numbers [ Google – Microsoft – Amazon ]

Edit Distance of Two Given String [ Amazon ]

Find K-Palindrome of a string [ Amazon]

Kadane’s Algorithm [ Macrosoft – Amazon – FlipKart ]

Maximum Product Sub array [ Microsoft – Amazon ]

Archives

Categories