1
\$\begingroup\$

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<stdio.h>
#pragma GCC optimize("O2") 

int main()
{
    long int c,d,j,N,Q;
    int fagvar=0;
    scanf("%ld %ld\n",&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("%d\n",0);
            fagvar=0;
        }
        else
        {
            printf("%d\n",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.

\$\endgroup\$
0
5
\$\begingroup\$

Code

#pragma GCC optimize("O2")

Normally we just pass that as a compiler flag, so we don't get "unrecognised pragma" 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 <stdint.h>) 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("%ld %ld\n",&N,&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: "What's the worst-case input this algorithm could be given?". 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).

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Good point about the #pragma. I somehow overlooked that. \$\endgroup\$ – Edward Jan 16 at 16:33
  • 1
    \$\begingroup\$ Thank you for your answer. The new algorithm as far as I can understand means that I should compute and store remainders(0 or 1) of all the numbers and then take the cummulative. i.e. [0,1,1,0,0,0,0,1,0,1]---->[0,1,2,2,2,2,2,3,3,4] so that I would just need to check if the left input and right input are equal. This means the complexity is--> O(n)+O(q) which is a very big improvement. Aaaah thanks a lot. \$\endgroup\$ – the_illuminated2003 Jan 16 at 17:59
  • \$\begingroup\$ That wasn't quite the solution I had in mind, but is probably better than what I was thinking. It's nice when I give a hint instead of spelling out in detail (because you're here to learn rather than be spoon-fed), and the result is that we both learn! I did mean to say that would be O(n+q), but I'm pleased that you worked it out for yourself. Edward's answer is also good; his suggestion uses less storage, traded for a cost in lookup time (greatly dependent on the odd/even balance of the input). \$\endgroup\$ – Toby Speight Jan 16 at 22:40
  • 1
    \$\begingroup\$ I realized there were some caveats to the cumulative. Although they can be fixed, but for anyone interested, instead of writing [0,1,2,2,2,2,2,3,3,4] one should write [0,1,2,3,4,4,4,4,5,6,7] now, the edge cases won't fail because the odd numbers are always at a different elevation than the even ones. \$\endgroup\$ – the_illuminated2003 Jan 17 at 3:52
  • 1
    \$\begingroup\$ @Kelly - there can't be -1, because we're counting numbers modulo two - we're adding either 0 or 1 at each step. I was loose with terminology: I should have said "running count of odd numbers". \$\endgroup\$ – Toby Speight Jan 17 at 19:15
5
+50
\$\begingroup\$

Here are some things that may help you improve your code.

Choose better variable names

I understand that N and Q are used within the problem description, but c and d are not and are very short and non-descriptive names.

Add comments

Comments do not add to compile time and help you (and others!) keep track of what is happening in the code.

Add error checking

One of the things I dislike about many of the programming contests is that they assume perfect input. In the real world, external data is not always formatted perfectly, so we would expect to do things like compensate for non-digit input or unexpected end of input. The obvious way to do this is to check the return value of scanf to make sure it actually read the values intended.

Rethink the algorithm

When we or numbers together the result is odd if any of the numbers was odd. Further, we can tell that a number is odd just by looking at the low bit of the number. In this problem, the result of a query can only be 1 (indicating that the result is even) if all of the values in the span are even. This suggests a much more elegant algorithm. Instead of storing all of the input numbers, just note the beginning and ending of each span of even numbers. Then for the queries, see if the values L and R lie completely within a single span. Here's one way to do that:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main()
{
    // N is number of input numbers
    // Q is number of input queries
    long N, Q;
    if (scanf("%ld %ld\n", &N, &Q) != 2) {
        return EXIT_FAILURE;
    }
    typedef struct {
        long begin;
        long end;
    } span;
    span even_spans[(N+1)/2];
    long span_count = 0;
    long i;
    bool in_span = false;
    /*
     * Read each number from the input,
     * and only examine the low bit.
     */
    for (i = 0; N--; ++i) {
        long m;
        if (scanf("%ld", &m) != 1) {
            return EXIT_FAILURE;
        }
        if (m & 1) {
            if (in_span) {
                even_spans[span_count++].end = i;
                in_span = false;
            }
        } else {  // it's even number
            if (!in_span) {
                even_spans[span_count].begin = i;
                in_span = true;
            }
        }
    }
    if (in_span) {
        even_spans[span_count++].end = i;
    }
    /* 
     * Process Q queries each of 
     * which is a pair of indices L, R
     */
    while (Q--) {
        long L, R;
        if (scanf("%ld %ld", &L, &R) != 2) {
            return EXIT_FAILURE;
        }
        // compensate for 1-based values
        --L;
        --R;
        for (i = 0; i < span_count && L > even_spans[i].end; ++i) {
        }
        // only even if L and R are in the same even span
        puts(i < span_count && L >= even_spans[i].begin 
                 && R < even_spans[i].end ? "1" : "0");
    }
}

How it works

To explain in a bit more detail how this works, first let's consider a short input file.

test.in

11 5
1 2 4 6 5 8 10 11 12 14 16
1 5
1 4
2 3
2 4
2 5

Here's what the input looks like to this algorithm:

Input array:

index number odd/even
0 1 odd
1 2 even
2 4 even
3 6 even
4 5 odd
5 8 even
6 10 even
7 11 odd
8 12 even
9 14 even
10 16 even

Here is the array of even spans that it creates:

span number begin end
0 1 4
1 5 7
2 8 11

Note that each span begins with the index of the first even number in a span, and ends one index after the final even number in a span.

Now for each of the query pairs \$L, R\$ mathematically the query is this

$$ \exists s \in S| ( L >= s_{\text{begin}}) \land (R < s_{\text{end}}) $$

Or in English, "there exists a span \$s\$ in the set of all spans \$S\$ such that \$L\$ is greater than or equal to \$s_{\text{begin}}\$ and \$R\$ is less than \$s_{\text{end}}\$. This code does a simple linear search; for huge data sets a binary search might be used.

Epilogue

Although the code above works, in that it produces correct answers, it takes much more time than the original version. If we combine @TobySpeight's excellent insight of storing a count of odd numbers instead of the original input array with the observation expressed here that a span will only result in an even number if the \$L,R\$ span lies completely within a span of even numbers, we can generate a much faster program at the expense of using more memory. Here's the code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    unsigned long N, Q;
    if (scanf("%lu %lu\n", &N, &Q) != 2)
    return EXIT_FAILURE;
    unsigned odd[N+1];
    unsigned oddcount = 0;
    unsigned *ptr = odd;
    for (++ptr; N--; ++ptr) {
        long m;
        if (scanf("%ld", &m) != 1)
            return EXIT_FAILURE;
        m &= 1;
        if (m) {
            oddcount += 2;
        } 
        *ptr = oddcount | m;
    }
    /* 
     * Process Q queries each of 
     * which is a pair L, R
     */
    unsigned long L, R;
    while (Q--) {
        if (scanf("%lu %lu", &L, &R) != 2)
            return EXIT_FAILURE;
        puts(odd[L] != odd[R] || odd[L] & 1 ? "0" : "1");
    }
}

How it works

As suggested by @TobySpeight, the array keeps track of the count of odd numbers. It allocates \$N+1\$ array items in the odd array and starts at odd[1] to eliminate the need for adjusting the 1-based query values. The addition is that within each array item we actually store two things: whether the particular input number was odd or even (bit 0) and the count of odd numbers so far (all the other bits of the unsigned value). Queries are handled by testing three conditions:

  1. odd[L] != odd[R] true if there were any odd numbers between
  2. odd[L] & 1 true if the left limit was an odd number
  3. odd[R] & 1 true if the right limit was an odd number

If any of these conditions are true, then the answer is 0 indicating an odd resulting value, otherwise the answer is 1 indicating an even resulting value. In reality, only the first two tests are needed, since the third test cannot be true if neither of the first two are.

Limitations

Although the program reads in unsigned long values for both \$N\$ and \$Q\$, the count of odd numbers is stored in an unsigned value. Further, we limit the range even more by using one bit of that number to indicate an odd or even value. Although the size of an unsigned is implementation-defined, the language of the standard yields the result that it must be at least 16 bits. Since we use one of those bits, the guaranteed maximum uniquely representable count is \$2^{15} - 1 = 32,767\$. After that, the value silently rolls over to zero. What that means for this program is that if the program's input ever has a span of odd numbers with a length that is an exact integral multiple of 32,768 (on systems with a 16-bit int) a query that picks a left location in the even span to the left of it, and a right location in the even span to the right of it, the program will falsely claim that the result is even. For systems with a 32-bit int, the value is 2,147,483,648.

If each input number is randomly selected, the probability that any given number is odd is \$P=\frac{1}{2} = 0.5\$. So the probability of randomly selecting 32,768 odd numbers in a row is \$3.052 \times 10^{-5}\$ or about 0.003%. The probability of selecting 2,147,483,648 odd numbers in a row is \$4.657 \times 10^{-10}\$ or about 0.000000047%. (For reference, according to this article, this is about ten times less likely than you winning the >US$700M Powerball lottery jackpot. I say "you" because I never buy lottery tickets; a practice which doesn't significantly alter my odds of winning!) However, we have no guarantee that the input values are selected randomly, and if I were running the contest, I would deliberately choose such inputs.

Interestingly, perhaps, it's on exactly this kind of input, with long spans of either even or odd numbers, that the first version I posted above works very well.

So the conclusion is that the program above is guaranteed to fail for certain ranges and types of values; whether that's acceptable is up to you.

\$\endgroup\$
17
  • \$\begingroup\$ I think I do not understand what you meant by span. Please elaborate on that. Also, there is possibly a minor flagging (0 or 1) error in your code because it failed when I tried it. (sorry, I don't have the test cases, neither they are public). Also, the single bit idea is marvelous and will help if the elements get big hence increasing modulo's complexity! \$\endgroup\$ – the_illuminated2003 Jan 16 at 18:07
  • \$\begingroup\$ I found the flaw. Input 6 7 1 4 5 7 4 6 1 1 2 2 2 3 3 4 4 4 5 5 6 6 Copy pasting wont be a problem. You would see that 6 6 is returned false which should have been 1 \$\endgroup\$ – the_illuminated2003 Jan 16 at 19:55
  • \$\begingroup\$ apparently if sequence is 1 4 8 10 4 6 the code will work as intended. But if, 1 4 5 10 4 6 it will fail \$\endgroup\$ – the_illuminated2003 Jan 16 at 19:59
  • \$\begingroup\$ There was a typo in the code. My apologies. \$\endgroup\$ – Edward Jan 16 at 22:29
  • 1
    \$\begingroup\$ Also FWIW, we can combine Toby Speight's excellent insight with the notion of spans of even numbers. I wrote this implementation to illustrate. \$\endgroup\$ – Edward Jan 18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.