Querying the probability of choosing even or odd elements in a subarray I have written a code where I have an array and I need to print the probability of picking an even/odd number in the given range in the array. 

If probability is 0 or 1, I have to print so. And if the probability is say 2/4, I have to reduce it to minimal form and print the output as "1 2" which means 1/2. I have written the below code which handles all these perfectly. But it is taking more than 3 seconds to execute so it is resulting in a timeout as the given time limit is 3 seconds for this.

How do I optimize this further?



#include&lt;stdio.h&gt;
int gcd(int u,int v)
{
int shift;
if(u==0) return v;
if(v==0) return u;
shift = __builtin_ctz(u | v);
u &gt;&gt;= __builtin_ctz(u);
do {
    v &gt;&gt;= __builtin_ctz(v);
    if(u&gt;v) {
        unsigned int t=v;
        v=u;
        u=t;
    }
    v = v-u;
} while(v!=0);
return u &lt;&lt; shift;
}
void query(char *arr, int qtype, int l, int r, char v)
{
int q=r-l+1;
int g1=1,g2=1;

int peven=0,podd=0;
for(int i=l-1;i&lt;r;i++)
{
    if(qtype==2 &amp;&amp; v)
        arr[i]=(arr[i]^v);
    if(qtype == 1)
    {
        if(arr[i])
        podd++;
    }
    else if(qtype == 0)
    {
        if(!(arr[i]))
        peven++;
    }
}

switch(qtype)
{
case 0:
{
    if(peven == 0)
        printf("0\n");
    else if(peven == q)
        printf("1\n");
    else
    {
        g1=gcd(peven,q);
        if(g1!=1)
        {
            peven/=g1;
            q/=g1;
        }
        printf("%d %d\n",peven,q);
    }
    break;
}

case 1:
{
    if(podd == 0)
        printf("0\n");
    else if(podd == q)
        printf("1\n");
    else 
    {
        g2=gcd(podd,q);
        if(g2!=1)
        {
            podd/=g2;
            q/=g2;
        }
        printf("%d %d\n",podd,q);
    }
    break;
}
default:
    break;
}

}


int main()
{
int T;

scanf("%d",&amp;T);

while(T--)
{
    int arr_size;
    scanf("%d",&amp;arr_size);

    int q;
    scanf("%d",&amp;q);

    char *arr=(char *)malloc(arr_size * sizeof(char));
    for(int i=0; i&lt;arr_size;i++)
    {
        int x;
        scanf("%d",&amp;x);
        arr[i]=(char)(x&amp;1);

    }
    while(q--)
    {
        int qtype,l,r;
        char v;

        scanf("%d%d%d",&amp;qtype,&amp;l,&amp;r);


        if(qtype==2)
        {
            int y;
            scanf("%d",&amp;y);
            v=(char)(y&amp;1);

        }

        query(arr,qtype,l,r,v);
    }
    free(arr);
}
return 0;
}



  Format of the input file:
  
  
  First line : T i.e Number of testcases. 
  For each testcase:
  
  
  First line : Two space separated integers N and Q.
  Second line : N space separated integers denoting the array.
  Next Q lines ; Space separated integers representing a query.
  
  
  
  Queries can be:
  
  
  0 L R :- You have to find and print the probability of choosing an even number from the segment [L,R] (both Inclusive).
  1 L R :- You have to find and print the probability of choosing an odd number from the segment [L,R] (both Inclusive).
  2 L R K :- You have to add number K to all the elements in the range, changing the values for subsequent queries
  
  
  Format of the output file:
  
  
  Output the answer to each query in a separate line. 
  
  
  Constraints:
  
  1&lt;= N,Q,K &lt;= 1000000
  
  Sample input;

1
5 3
6 5 2 1 7 
0 2 2
2 2 5 3
1 2 5

  
  Sample Output:

0
1 4

  
  Explanation: For query 3 numbers in the range [2,5] are {8,5,4,10}
  Hence probability of choosing a odd number is 1/4.
Well, first you should properly format your code. Readability means maintainability, and fewer bugs.

Try to avoid type-conversions and casts. They are danger-points, and if you use a decent warning-level, your compiler should warn about potentially dangerous type-conversions at least.
In gcd() you use int everywhere but once, where you use unsigned int. Fix that.

You have three query-types, and you seem to desperately want to make them share code. Don't do that! Branch-misprediction is expensive, and moving work out of inner loops is always a win. Hopefully, your compiler will do it for you, so the compiled code does not suffer from your choice like the source code does.

Take a look at which compound-assignment-operators are available. They make assignments more readable and concise.

Try to declare your variables in the smallest scope you can for better readability. Even if you insist on strict C89 with GCC builtins, you can go further.

Don't assume success! scanf() and malloc() can fail, so check for it.

Don't cast the result of malloc(). It's unnecessary and error-prone.

Normalize the range early-on for ease of use. A pointer and a length are sufficient unless you need the position in the surrounding array, and you don't.


You might want to experiment with using a bit-vector, or representing the array as spans of odd / even numbers.