Programming Solutions
A solved hackerearth coding problem
Given N numbers as input, and Q queries you have to print the output of each query on a separate new line.
Each query is of the form, L R. You have to print the largest exponent of 2 that is the divisor of product of all numbers from indices L to R.
Input Format:
First line contains an integers N. Next line contains N space separated integers, the array A[]. Next line contains an integer Q. Next Q lines contains two integers each, L R.
Output Format:
Print the answer as specified.
Contraints:
1 ≤ N,Q ≤ 105
1 ≤ A[i] ≤ 1018
1 ≤ L ≤ R ≤ N
Problem Setter : Saurabh Mishra
Sample Input
3
2 5 26
2
1 2
1 3
Sample Output
1
2
Explanation
First Query - 1 2, product is 2*5 = 10
Largest exponent of 2 that divides it is 2^1, hence answer 1.
Second Query - 1 3, product is 2*5*26 = 260
Largest exponent of 2 that divides it is 2^2 i.e., 4 , hence answer 2.
Babu's Solution in c
#include <stdio.h>
#include <inttypes.h>
int main()
{
int n,q,l,r,i,j;
uint64_t ai,s;
scanf("%d",&n);
//printf("%d\n",n);
int a[n];
for (i=0;i<n;i++)
{
scanf("%lu",&ai);
//printf("%lu\n",ai);
//for (j=0;ai%2==0;j++,ai/=2);
j=0;
while (ai%2==0) {j++;ai/=2;}
a[i]=j;
}
scanf("%d",&q);
for (i=0;i<q;i++)
{
scanf("%d %d",&l,&r);
s=0;
for (j=l;j<=r;j++)
{
s+=a[j-1];
}
printf("%lu\n",s);
}
return 0;
}
Comments
Post a Comment