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

Popular posts from this blog

ഭാഗ്യാതിരേക

ചോയിക്കുട്ടി കഥകൾ - രണ്ട് : അനാരോഗ്യമത്സരം

ജയം ഉറപ്പുള്ള കളികൾ