Determine whether bitwise-OR of sub-array is odd 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 (Qi) 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 [1]; 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.

The code O(nq)
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-separated integers L and R in each line.
#include&lt;stdio.h&gt;
#pragma GCC optimize(&quot;O2&quot;) 

int main()
{
    long int c,d,j,N,Q;
    int fagvar=0;
    scanf(&quot;%ld %ld\n&quot;,&amp;N,&amp;Q);
    int a[N];
    int i=0;
    while(N--)
    {
        scanf(&quot;%ld&quot;,&amp;a[i]);
        i++;
    }
    while(Q--)
    {
        scanf(&quot;%ld %ld&quot;,&amp;c,&amp;d);
        for(j=c-1;j&lt;d;j++)
        {
            if (a[j]%2==1)
            {
                fagvar=1;
                break;
            }
        }
        if (fagvar==1)
        {
            printf(&quot;%d\n&quot;,0);
            fagvar=0;
        }
        else
        {
            printf(&quot;%d\n&quot;,1);
        }
    }
    return 0;
}


After 2 answers and a rethinking of algorithm, the final complexity falls at O(n+q). Note: Since this was a competitive problem and I probably won't revisit the same program I haven't added any extra readability. The reader is free to edit my code as required. For the algorithm, visit Toby Speight's comment section.
Visit here for the code. For an amalgamation of spanning over even numbers and Toby's method, visit here.
Code

#pragma GCC optimize(&quot;O2&quot;)


Normally we just pass that as a compiler flag, so we don't get &quot;unrecognised pragma&quot; warnings from other compilers.

    long int c,d,j,N,Q;


These are poor names - they tell us very little about what they are used for.
The number of array elements and the number of queries can't be negative.  I suggest size_t (from &lt;stdint.h&gt;) would be better than long for these.  Also consider what range is required for the other values (the challenge should state these bounds).  You might want to use the int_fastX_t and int_leastX_t families to ensure the required range.

    scanf(&quot;%ld %ld\n&quot;,&amp;N,&amp;Q);


Don't throw away the return value from scanf() like that.  It's important to know how many conversions were successfully performed before attempting to use the assigned values.
Algorithm
This is on average, much less computation than the naive brute-force algorithm, since we stop examining the array once we find an odd number.
Something to consider, especially for programming challenges, is that we often talk of average-case complexity using big-O notation, but it can be more helpful to think like an adversary: &quot;What's the worst-case input this algorithm could be given?&quot;.  The test cases are likely to include some arrays which are all odd or all even - the former being very expensive for this algorithm.
If we have many queries, we can spend a little time creating a structure to make each query constant-time.  The way I would approach this is probably to have an array of size_t that stores the running count of odd numbers.  Then, given a query Q(m,n), look at odd_count[n]; if it's equal to odd_count[m], we have only even numbers in the range, else we have at least one odd number.  Note that we don't need to actually store the input array, as we'll only use the running total.  Obviously, adjust m and n before lookup if these are inclusive in the challenge (it's a little unclear in your summary, but I assume more rigorously defined in the original).