Ad Hoc – Live with passion

Super Ugly Number – Extension of Ugly Number Problem

Asif NaeemAugust 5, 2017

Problem: The problem is an extension of Ugly number problem. Problem Link : Here [Courtesy geeksforgeeks]

#include <stdio.h>
#include <iostream>

using namespace std;

int _min(int arr[],int k)
{
	int m= arr[0];
	for(int i=1;i<k;i++)
	{
		if(m>arr[i])
		m=arr[i];
	}
	return m;
}

int SuperUgly(int n,int k,int primes[])
{
	int min_val;
	int superUgly[n];
	int tmp[k];
	int prime_iterator_count[k];
	for(int i=0;i<k;i++)
		prime_iterator_count[i]=0;
	superUgly[0]=1;
	
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<k;j++)
		{
			tmp[j] = superUgly[ prime_iterator_count[j] ] * primes[j];
		}
		min_val = _min(tmp,k);
		superUgly[i]=min_val;
		for(int j=0;j<k;j++)
		{
			if(min_val==tmp[j])
			prime_iterator_count[j]++;
		}
	}
	return superUgly[n-1];
}

int main()
{
	int primes[100];
	int t,n,k;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=0;i<k;i++)
			scanf("%d",&primes[i]);
		cout<<SuperUgly(n,k,primes)<<endl;
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <stdio.h>

#include <iostream>

using namespace std;

int _min(int arr[],int k)

{

int m= arr[0];

for(int i=1;i<k;i++)

{

if(m>arr[i])

m=arr[i];

}

return m;

}

int SuperUgly(int n,int k,int primes[])

{

int min_val;

int superUgly[n];

int tmp[k];

int prime_iterator_count[k];

for(int i=0;i<k;i++)

prime_iterator_count[i]=0;

superUgly[0]=1;

for(int i=1;i<n;i++)

{

for(int j=0;j<k;j++)

{

tmp[j] = superUgly[ prime_iterator_count[j] ] * primes[j];

}

min_val = _min(tmp,k);

superUgly[i]=min_val;

for(int j=0;j<k;j++)

{

if(min_val==tmp[j])

prime_iterator_count[j]++;

}

return superUgly[n-1];

}

int main()

{

int primes[100];

int t,n,k;

cin>>t;

while(t--)

{

cin>>n>>k;

for(int i=0;i<k;i++)

scanf("%d",&primes[i]);

cout<<SuperUgly(n,k,primes)<<endl;

}

Ugly Number Problem

Asif NaeemAugust 1, 2017

Problem: The problem of ugly number is a common DP problem. Description: Ugly numbers are positive numbers whose prime factors only include 2,3,5,7. For example, 6,8 are ugly while 14 is not ugly since it includes another prime factor 7.Note that 1 is typically treated as an ugly number. courtesy: leetcode.com

#include <stdio.h>
#include <iostream>

using namespace std;

int _min(int a,int b,int c)
{
	if(a<=b && a<=c)
	{
		return a;
	}
	if(b<=a && b<=c)
	{
		return b;
	}
	if(c<=b && c<=a)
	{
		return c;
	}
}

int main()
{
	int two_used=0,three_used=0,five_used=0;
	int next_ugly_number;
	int a,b,c;
	int ugly[155];
	
	ugly[0]=1;
	
	for(int i=1;i<155;i++)
	{
		a = ugly[two_used]*2;
		b = ugly[three_used]*3;
		c = ugly[five_used]*5;
		
		next_ugly_number = _min(a,b,c);
		ugly[i]=next_ugly_number;
		if(next_ugly_number==a)
		two_used++;
		if(next_ugly_number==b)
		three_used++;
		if(next_ugly_number==c)
		five_used++;
	}
	//cout<<_min(5,2,3)<<endl;
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		cout<<ugly[n-1]<<endl;
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <stdio.h>

#include <iostream>

using namespace std;

int _min(int a,int b,int c)

{

if(a<=b && a<=c)

{

return a;

}

if(b<=a && b<=c)

{

return b;

}

if(c<=b && c<=a)

{

return c;

}

int main()

{

int two_used=0,three_used=0,five_used=0;

int next_ugly_number;

int a,b,c;

int ugly[155];

ugly[0]=1;

for(int i=1;i<155;i++)

{

a = ugly[two_used]*2;

b = ugly[three_used]*3;

c = ugly[five_used]*5;

next_ugly_number = _min(a,b,c);

ugly[i]=next_ugly_number;

if(next_ugly_number==a)

two_used++;

if(next_ugly_number==b)

three_used++;

if(next_ugly_number==c)

five_used++;

}

//cout<<_min(5,2,3)<<endl;

int t,n;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

cout<<ugly[n-1]<<endl;

}

return 0;

}

Number that are not divisible [Paytm]

Asif NaeemAugust 1, 2017

Problem: Find the number of non-divisible numbers in a range starting from 1 to N, for a given set. Problem Link [Courtesy: geeksforgeeks.org] Appeared as interview question in Paytm. Solution: The given set is {2,3,4,5,6,7,8,9,10}. The set can be minimized to {2,3,5,7} as these are the prime numbers and rest of the numbers of the

Continue Reading “Number that are not divisible [Paytm]” →

661

Asif NaeemApril 14, 2016

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

int capacity[21];
bool isTurnOn[21];
int main()
{
	int n,m,c;
	int MX=0;
	int device;
	int kase=1;
	bool IsFUSE;
	long long total;
	while(scanf("%d%d%d",&n,&m,&c))
	{
		if(n+m+c==0)
		break;
		//memset(capacity,0,sizeof(capacity));
		//memset(isTurnOn,0,sizeof(isTurnOn));
		IsFUSE=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&capacity[i]);
			isTurnOn[i]=0;
		}
		total=0;
		MX=0;
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&device);
			if(IsFUSE)
			continue;
			if(isTurnOn[device]==0)
			{
				isTurnOn[device]=1;
				total+=capacity[device];
			}
			else if(isTurnOn[device]==1)
			{
				isTurnOn[device]=0;
				total-=capacity[device];
			}

			if(total>c)
			{
				IsFUSE=1;
			}
			if(total>MX)
			MX=total;
		}
		printf("Sequence %d\n",kase++);
		if(IsFUSE)
		printf("Fuse was blown.\n");
		else
		{
			printf("Fuse was not blown.\n");
			printf("Maximal power consumption was %d amperes.\n",MX);
		}
		printf("\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

int capacity[21];

bool isTurnOn[21];

int main()

{

int n,m,c;

int MX=0;

int device;

int kase=1;

bool IsFUSE;

long long total;

while(scanf("%d%d%d",&n,&m,&c))

{

if(n+m+c==0)

break;

//memset(capacity,0,sizeof(capacity));

//memset(isTurnOn,0,sizeof(isTurnOn));

IsFUSE=0;

for(int i=1;i<=n;i++)

{

scanf("%d",&capacity[i]);

isTurnOn[i]=0;

}

total=0;

MX=0;

for(int i=1;i<=m;i++)

{

scanf("%d",&device);

if(IsFUSE)

continue;

if(isTurnOn[device]==0)

{

isTurnOn[device]=1;

total+=capacity[device];

}

else if(isTurnOn[device]==1)

{

isTurnOn[device]=0;

total-=capacity[device];

}

if(total>c)

{

IsFUSE=1;

}

if(total>MX)

MX=total;

}

printf("Sequence %d\n",kase++);

if(IsFUSE)

printf("Fuse was blown.\n");

else

{

printf("Fuse was not blown.\n");

printf("Maximal power consumption was %d amperes.\n",MX);

}

printf("\n");

}

return 0;

}

10102

Asif NaeemNovember 28, 2015

Critical t get the question but easy to solve. Problem asks to find the maximum length of minimum distance.

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#include <fstream>
#include <string>
#include <algorithm>

#define INF 100000000
#define ll long long

using namespace std;

struct Cord{
	int x,y;
};
int M;
char gr[1010][1010];
char s[1010][1010];
vector<Cord> Ones,Threes;

int main()
{
	Cord tmp;
	int MX,dist,MN;
	while(scanf("%d",&M)!=EOF)
	{
		getchar();
		Threes.clear();
		Ones.clear();
		for(int i=0;i<M;i++)
		{
			scanf("%s",s[i]);
			for(int j=0;j<strlen(s[i]);j++)
			{
				if(s[i][j]=='1')
				{
					tmp.x = i;
					tmp.y = j;
					Ones.push_back(tmp);
				}
				if(s[i][j]=='3')
				{
					tmp.x = i;
					tmp.y = j;
					Threes.push_back(tmp);
				}
			}
		}
		MX = -1;
		for(int i=0;i<Ones.size();i++)
		{
			MN = INF;
			for(int j=0;j<Threes.size();j++)
			{
				dist = abs(Ones[i].x-Threes[j].x)+abs(Ones[i].y-Threes[j].y);
				if(dist<MN)
				MN =dist;
			}
			if(MX<MN)
			MX = MN;
		}
		printf("%d\n",MX);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <vector>

#include <stack>

#include <cmath>

#include <cstring>

#include <fstream>

#include <string>

#include <algorithm>

#define INF 100000000

#define ll long long

using namespace std;

struct Cord{

int x,y;

};

int M;

char gr[1010][1010];

char s[1010][1010];

vector<Cord> Ones,Threes;

int main()

{

Cord tmp;

int MX,dist,MN;

while(scanf("%d",&M)!=EOF)

{

getchar();

Threes.clear();

Ones.clear();

for(int i=0;i<M;i++)

{

scanf("%s",s[i]);

for(int j=0;j<strlen(s[i]);j++)

{

if(s[i][j]=='1')

{

tmp.x = i;

tmp.y = j;

Ones.push_back(tmp);

}

if(s[i][j]=='3')

{

tmp.x = i;

tmp.y = j;

Threes.push_back(tmp);

}

MX = -1;

for(int i=0;i<Ones.size();i++)

{

MN = INF;

for(int j=0;j<Threes.size();j++)

{

dist = abs(Ones[i].x-Threes[j].x)+abs(Ones[i].y-Threes[j].y);

if(dist<MN)

MN =dist;

}

if(MX<MN)

MX = MN;

}

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

}

return 0;

}

11661

Asif NaeemNovember 21, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <cstring>

using namespace std;

char s[2000000+10];

int main()
{
	int n,dist,prev_idx;
	char prev;
	bool first;
	while(scanf("%d",&n),n)
	{
		dist= n;
		first=0;
		scanf("%s",s);
		for(int i=0;i<n;i++)
		{
			//scanf("%c",&s[i]);
			if(s[i]=='Z')
			dist=0;
			if(s[i]=='R' && first==false)
			{
				prev='R';
				prev_idx=i;
				first=true;
				continue;
			}
			if(s[i]=='D' && first==false)
			{
				prev='D';
				prev_idx=i;
				first=true;
				continue;
			}
			if(first==1 && (s[i]=='D' || s[i]=='R'))
			{
				if(prev==s[i])
				{
					prev_idx=i;
				}
				else
				{
					if(dist>(i-prev_idx))
					dist=i-prev_idx;
					prev=s[i];
					prev_idx=i;
				}
			}
		}//for ends
		printf("%d\n",dist);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

#include <cstring>

using namespace std;

char s[2000000+10];

int main()

{

int n,dist,prev_idx;

char prev;

bool first;

while(scanf("%d",&n),n)

{

dist= n;

first=0;

scanf("%s",s);

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

{

//scanf("%c",&s[i]);

if(s[i]=='Z')

dist=0;

if(s[i]=='R' && first==false)

{

prev='R';

prev_idx=i;

first=true;

continue;

}

if(s[i]=='D' && first==false)

{

prev='D';

prev_idx=i;

first=true;

continue;

}

if(first==1 && (s[i]=='D' || s[i]=='R'))

{

if(prev==s[i])

{

prev_idx=i;

}

else

{

if(dist>(i-prev_idx))

dist=i-prev_idx;

prev=s[i];

prev_idx=i;

}

}//for ends

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

}

return 0;

}

11734

Asif NaeemOctober 20, 2015

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int t,kase=1;
	string org,ans,tmp1,tmp2;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		getline(cin,ans);
		getline(cin,org);
		if(org.size()==ans.size())
		{
			bool f=0;
			for(int i=0;i<org.size();i++)
			{
				if(org[i]!=ans[i])
				{
					f=1;break;
				}
			}
			if(f)
				printf("Case %d: Wrong Answer\n",kase++);
			else
				printf("Case %d: Yes\n",kase++);
		}
		else
		{
			tmp1="";tmp2="";
			for(int i=0;i<org.size();i++)
			{
				if(org[i]!=' ')
					tmp1.append(1u,org[i]);
			}
			for(int i=0;i<ans.size();i++)
			{
				if(ans[i]!=' ')
					tmp2.append(1u,ans[i]);
			}
			if(tmp1.size()!=tmp2.size())
			{
				printf("Case %d: Wrong Answer\n",kase++);
			}
			else
			{
				bool fl=0;
				for(int i=0;i<tmp1.size();i++)
				{
					if(tmp1[i]!=tmp2[i])
					{
						fl=1;break;
					}
				}
				if(fl)
					printf("Case %d: Wrong Answer\n",kase++);
				else
					printf("Case %d: Output Format Error\n",kase++);
			}
		}
	}
	return 0;
}

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

int t,kase=1;

string org,ans,tmp1,tmp2;

scanf("%d",&t);

getchar();

while(t--)

{

getline(cin,ans);

getline(cin,org);

if(org.size()==ans.size())

{

bool f=0;

for(int i=0;i<org.size();i++)

{

if(org[i]!=ans[i])

{

f=1;break;

}

if(f)

printf("Case %d: Wrong Answer\n",kase++);

else

printf("Case %d: Yes\n",kase++);

}

else

{

tmp1="";tmp2="";

for(int i=0;i<org.size();i++)

{

if(org[i]!=' ')

tmp1.append(1u,org[i]);

}

for(int i=0;i<ans.size();i++)

{

if(ans[i]!=' ')

tmp2.append(1u,ans[i]);

}

if(tmp1.size()!=tmp2.size())

{

printf("Case %d: Wrong Answer\n",kase++);

}

else

{

bool fl=0;

for(int i=0;i<tmp1.size();i++)

{

if(tmp1[i]!=tmp2[i])

{

fl=1;break;

}

if(fl)

printf("Case %d: Wrong Answer\n",kase++);

else

printf("Case %d: Output Format Error\n",kase++);

}

return 0;

}

11936

Asif NaeemOctober 19, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

int main()
{
	int n,a,b,c;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d%d",&a,&b,&c);
		bool OK=1;
		if(a>=(b+c))
		OK=0;
		if(b>=(a+c))
		OK=0;
		if(c>=(a+b))
		OK=0;
		if(OK)
		printf("OK\n");
		else
		printf("Wrong!!\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

int main()

{

int n,a,b,c;

scanf("%d",&n);

while(n--)

{

scanf("%d%d%d",&a,&b,&c);

bool OK=1;

if(a>=(b+c))

OK=0;

if(b>=(a+c))

OK=0;

if(c>=(a+b))

OK=0;

if(OK)

printf("OK\n");

else

printf("Wrong!!\n");

}

return 0;

}

12136

Asif NaeemSeptember 22, 2015

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
	int t;
	int kase=1;
	int hr1,hr2,hr3,hr4;
	int t1,t2,t3,t4;
	int mn1,mn2,mn3,mn4;
	string str1,str2,str3,str4;
	scanf("%d",&t);

	while(t--)
	{
		cin>>str1>>str2;
		cin>>str3>>str4;

		hr1=hr2=hr3=hr4=0;
		mn1=mn2=mn3=mn4=0;

		hr1=str1[0]-'0';hr1*=10;
		hr1+=(str1[1]-'0');

		hr2=str2[0]-'0';hr2*=10;
		hr2+=(str2[1]-'0');

		hr3=str3[0]-'0';hr3*=10;
		hr3+=(str3[1]-'0');

		hr4=str4[0]-'0';hr4*=10;
		hr4+=(str4[1]-'0');

		mn1=str1[3]-'0';mn1*=10;
		mn1+=(str1[4]-'0');

		mn2=str2[3]-'0';mn2*=10;
		mn2+=(str2[4]-'0');

		mn3=str3[3]-'0';mn3*=10;
		mn3+=(str3[4]-'0');

		mn4=str4[3]-'0';mn4*=10;
		mn4+=(str4[4]-'0');

		t1 = hr1*60+mn1;
		t2 = hr2*60+mn2;
		t3 = hr3*60+mn3;
		t4 = hr4*60+mn4;

		/*
		if(hr3>=hr1 && hr3<=hr2)
		{
			printf("Case %d: Mrs Meeting\n",kase++);
		}
		else if(hr3==hr2)
		{
			if(mn3<=mn2)
			printf("Case %d: Mrs Meeting\n",kase++);
			else
			printf("Case %d: Hits Meeting\n",kase++);
		}
		else if(hr4==hr1)
		{
			if(mn1<=mn4)
			printf("Case %d: Mrs Meeting\n",kase++);
			else
			printf("Case %d: Hits Meeting\n",kase++);
		}
		else
		printf("Case %d: Hits Meeting\n",kase++);
		*/
		if(t1>=t3 && t1<=t4)
		printf("Case %d: Mrs Meeting\n",kase++);
		else if(t3>=t1 && t3<=t2)
		printf("Case %d: Mrs Meeting\n",kase++);
		else
		printf("Case %d: Hits Meeting\n",kase++);

	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <queue>

#include <sstream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

int main()

{

int t;

int kase=1;

int hr1,hr2,hr3,hr4;

int t1,t2,t3,t4;

int mn1,mn2,mn3,mn4;

string str1,str2,str3,str4;

scanf("%d",&t);

while(t--)

{

cin>>str1>>str2;

cin>>str3>>str4;

hr1=hr2=hr3=hr4=0;

mn1=mn2=mn3=mn4=0;

hr1=str1[0]-'0';hr1*=10;

hr1+=(str1[1]-'0');

hr2=str2[0]-'0';hr2*=10;

hr2+=(str2[1]-'0');

hr3=str3[0]-'0';hr3*=10;

hr3+=(str3[1]-'0');

hr4=str4[0]-'0';hr4*=10;

hr4+=(str4[1]-'0');

mn1=str1[3]-'0';mn1*=10;

mn1+=(str1[4]-'0');

mn2=str2[3]-'0';mn2*=10;

mn2+=(str2[4]-'0');

mn3=str3[3]-'0';mn3*=10;

mn3+=(str3[4]-'0');

mn4=str4[3]-'0';mn4*=10;

mn4+=(str4[4]-'0');

t1 = hr1*60+mn1;

t2 = hr2*60+mn2;

t3 = hr3*60+mn3;

t4 = hr4*60+mn4;

if(hr3>=hr1 && hr3<=hr2)

{

printf("Case %d: Mrs Meeting\n",kase++);

}

else if(hr3==hr2)

{

if(mn3<=mn2)

printf("Case %d: Mrs Meeting\n",kase++);

else

printf("Case %d: Hits Meeting\n",kase++);

}

else if(hr4==hr1)

{

if(mn1<=mn4)

printf("Case %d: Mrs Meeting\n",kase++);

else

printf("Case %d: Hits Meeting\n",kase++);

}

else

printf("Case %d: Hits Meeting\n",kase++);

if(t1>=t3 && t1<=t4)

printf("Case %d: Mrs Meeting\n",kase++);

else if(t3>=t1 && t3<=t2)

printf("Case %d: Mrs Meeting\n",kase++);

else

printf("Case %d: Hits Meeting\n",kase++);

}

return 0;

}

12468

Asif NaeemSeptember 16, 2015

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdlib>

#define INF 1000000
#define ll long long

using namespace std;

int main()
{
	int m,n,diff1,diff2;
	while(scanf("%d%d",&m,&n) && m!=-1 && n!=-1)
	{
		if(m==-1 && n==-1)
		break;
		diff1 = abs(m-n);
		if(diff1<=50)
		printf("%d\n",diff1);
		else
		printf("%d\n",100-diff1);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <cstdlib>

#define INF 1000000

#define ll long long

using namespace std;

int main()

{

int m,n,diff1,diff2;

while(scanf("%d%d",&m,&n) && m!=-1 && n!=-1)

{

if(m==-1 && n==-1)

break;

diff1 = abs(m-n);

if(diff1<=50)

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

else

printf("%d\n",100-diff1);

}

return 0;

}

Category: Ad Hoc

Super Ugly Number – Extension of Ugly Number Problem

Ugly Number Problem

Number that are not divisible [Paytm]

661

10102

11661

11734

11936

12136

12468

Archives

Categories