#include<stdio.h>
int main() {
int n,t,flag1,flag2,j,total=0,i;
int m;
scanf("%i %i", &n, &m);
int a[n],b[m];
for (i = 0; i < n; i++)
scanf("%i",&a[i]);
for (i = 0; i < m; i++)
scanf("%i",&b[i]);
for(t=n;t<=b[0];t++)
{
flag1=0;
flag2=0;
for(i=0;i<n;i++)
{
if(t%a[i] !=0)
{
flag1=1;
break;
}
}
if(flag1 == 0)
{
for(j=0;j<m;j++)
{
if(b[j]%t !=0)
{
flag2=1;
break;
}
}
}
if(flag1 == 0 && flag2 == 0)
total++;
}
printf("%d\n", total);
return 0;
}
can you please explain this
ReplyDeletegiven in problem statement
DeleteLet us consider one number, say x
each element in first array divides x
i.e, x%first_array_element is zero
first_array_elements must be <=x (as first_array_element is in denominator & denominator must be < numerator(x))
each element of second array when divided by x leaves a reminder zero i.e,
second_array_element%x is zero
so second array elements must be >=x
so the answer will be between a[n-1] and b[0]
For this don't we have to sort array first
DeleteNo..You need not sort. As you can start the loop from n i.e, for(t=n;t<=b[0];t++)
DeleteI have changed the code such that even beginners can understand my logic.
Could you please elaborate this?
ReplyDelete1)only last member of firstarray may divide all and get remainder 0 if possible else only numbers greater than last member in first array can;
Delete2)so he initiated for loop with n as n will be surely less than the last member of first array as they are already given in ascending order;
3)then he tested, will every member of first array gives remainder 0 or not with anynumber starting from n;
4) if not flag 1 turns to 1 and breaks out of forloop;
he did samething with second array but in some different manner(will this number be divisible by every member of second array or not)
5)if both satisfies total will be incremented by 1;
6)finally we will gwt the count of total such type of numbers that satisfies the two given conditions
can we do without using flags??
ReplyDeletefor(t=n;t<=b[0];t++)
ReplyDeletehere why t=n?