Tag: making

Problem:
Given an array A of N integers, you will be asked Q queries. Each query consists of two integers L and R. For each query, find whether bitwise OR of all the array elements between indices L and R is even or odd.

My approach:
Accept the array of N integers. For any query (Q_i) scan the array of integers between the given limit. If an odd number is found (x%2==1) then raise a flag and terminate scanning. If flag is found raised tell that the result is odd, else say that it’s even.

On thinking further, I find myself at the dead end. I can’t optimize the code anymore. Only thing I can think of is instead of doing mod 2 I will check the last digit of each number and see if it is one of (0,2,4,6,8). Upon trying that, the time limit still expired (in context to competitive programming ⁽¹⁾; Note: the competition has ended a day ago and results declared). Anyways, my question is to find a better method if it exists or optimize the code below.

I assume that the time complexity is O(nQ) where n is the number of elements in the given range.

Assume array is 1-indexed.
Input
First line consists of two space-separated integers N and Q.
Next line consists of N space-separated array elements.
Next Q lines consist of two space-sepaprated integers L and R in each line.

#include<stdio.h>
#pragma GCC optimize("O2") 

int main()
{
    long int c,d,j,N,Q;
    int fagvar=0;
    scanf("%ld %ldn",&N,&Q);
    int a(N);
    int i=0;
    while(N--)
    {
        scanf("%ld",&a(i));
        i++;
    }
    while(Q--)
    {
        scanf("%ld %ld",&c,&d);
        for(j=c-1;j<d;j++)
        {
            if (a(j)%2==1)
            {
                fagvar=1;
                break;
            }
        }
        if (fagvar==1)
        {
            printf("%dn",0);
            fagvar=0;
        }
        else
        {
            printf("%dn",1);
        }
    }
    return 0;
}