c - Querying the probability of choosing even or odd elements in a subarray - Code Review Stack Exchange

i have written code have array , need print probability of picking even/odd number in given range in array.

if probability 0 or 1, have print so. , if probability 2/4, have reduce minimal form , print output "1 2" means 1/2. have written below code handles these perfectly. taking more 3 seconds execute resulting in timeout given time limit 3 seconds this.

how optimize further?

---

#include<stdio.h> int gcd(int u,int v) { int shift; if(u==0) return v; if(v==0) return u; shift = __builtin_ctz(u | v); u >>= __builtin_ctz(u); {     v >>= __builtin_ctz(v);     if(u>v) {         unsigned int t=v;         v=u;         u=t;     }     v = v-u; } while(v!=0); return u << 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<r;i++) {     if(qtype==2 && 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",&t);  while(t--) {     int arr_size;     scanf("%d",&arr_size);      int q;     scanf("%d",&q);      char *arr=(char *)malloc(arr_size * sizeof(char));     for(int i=0; i<arr_size;i++)     {         int x;         scanf("%d",&x);         arr[i]=(char)(x&1);      }     while(q--)     {         int qtype,l,r;         char v;          scanf("%d%d%d",&qtype,&l,&r);           if(qtype==2)         {             int y;             scanf("%d",&y);             v=(char)(y&1);          }          query(arr,qtype,l,r,v);     }     free(arr); } return 0; } 

format of input file:

• first line : t i.e number of testcases.

• for each testcase:

  • first line : 2 space separated integers n , q.

  • second line : n space separated integers denoting array.

  • next q lines ; space separated integers representing query.

queries can be:

• 0 l r :- have find , print probability of choosing number segment [l,r] (both inclusive).

• 1 l r :- have find , print probability of choosing odd number segment [l,r] (both inclusive).

• 2 l r k :- have add number k elements in range, changing values subsequent queries

format of output file:

• output answer each query in separate line.

constraints:

1<= n,q,k <= 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: query 3 numbers in range [2,5] {8,5,4,10} hence probability of choosing odd number 1/4.

i suspect you're being hit large "updates" number, since traverse entire interval while not doing in case.
earlier make decision not anything, faster can nothing.

there lot of intertwined logic , unnecessary branching in code; clean logic separating queries updates, , separate computation output.

something (using int instead of char):

/* turn 0 1 , vice versa in 'arr[l .. r]'. */ void flip(int* arr, int l, int r) {     (int = l; < r; i++)     {         arr[i] = 1 - arr[i];     } }  /* count number of occurrences of 'value' in 'arr[l .. r]'. */ int count(int* arr, int l, int r, int value) {     int number = 0;     (int = l; < r; i++) {         if (arr[i] == value) {             number += 1;         }     }     return number; }  int main() {     /* ... before ... */      while (q--) {         int qtype, l, r;         scanf("%d%d%d", &qtype, &l, &r);         if (qtype == 2) {             int y;             scanf("%d",&y);             if (y & 1) {                 /* when has effect. */                 flip(arr, l, r);             }         }         else {             int size = r - l + 1;             int occurrences = count(arr, l, r, qtype == 1 ? 1 : 0);             if (occurrences == 0) {                 printf("%d\n", 0);             }             else if (occurrences == size) {                 printf("%d\n", 1);             }             else {                 int divisor = gcd(occurrences, size);                 printf("%d %d\n", occurrences / divisor, size / divisor);             }         }     }     /* ... before ... */ }