# 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<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);
do {
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 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<= 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: For query 3 numbers in the range [2,5] are {8,5,4,10} Hence probability of choosing a odd number is 1/4.

• What aspect do you wish to optimize, and for what hardware? If you have many cores available, it's trivially easy to reduce latency by a few well-placed #pragma omp. But that obviously doesn't help throughput if you're already running many instances simultaneously. And the performance of the memory hierarchy will have a great effect on timings, too. – Toby Speight Oct 17 '17 at 15:19

## 3 Answers

1. Well, first you should properly format your code. Readability means maintainability, and fewer bugs.

2. 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.

3. 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.

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

5. 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.

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

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

8. 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.

• "Don't cast the result of malloc()" - and don't multiply its argument by 1 (i.e. sizeof (char))! – Toby Speight Oct 13 '17 at 9:32

I suspect that you're being hit by large "updates" with an even number, since you traverse the entire interval while not doing anything in that case.
The earlier you make the decision to not do anything, the faster you can do nothing.

There is also a lot of intertwined logic and unnecessary branching in the code; I would clean up the logic by separating queries from updates, and separate computation from output.

Something like this (using int instead of char):

/* Turn 0 into 1 and vice versa in 'arr[l .. r]'. */
void flip(int* arr, int l, int r)
{
for (int i = l; i < r; i++)
{
arr[i] = 1 - arr[i];
}
}

/* Count the number of occurrences of 'value' in 'arr[l .. r]'. */
int count(int* arr, int l, int r, int value)
{
int number = 0;
for (int i = l; i < r; i++) {
if (arr[i] == value) {
number += 1;
}
}
return number;
}

int main()
{
/* ... as 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) {
/* Only do this when it has an 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);
}
}
}
/* ... as before ... */
}


# Listen to your compiler

Before any refactoring, you should address the compiler warnings:

gcc-7 -std=c11 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds   -Wconversion    175458.c    -o 175458
175458.c: In function ‘gcd’:
175458.c:7:23: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
shift = __builtin_ctz(u | v);
^
175458.c:8:21: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
u >>= __builtin_ctz(u);
^
175458.c:10:25: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
v >>= __builtin_ctz(v);
^
175458.c:12:24: warning: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
unsigned int t=v;
^
175458.c:14:11: warning: conversion to ‘int’ from ‘unsigned int’ may change the sign of the result [-Wsign-conversion]
u=t;
^
175458.c: In function ‘main’:
175458.c:102:23: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
char *arr=(char *)malloc(arr_size * sizeof(char));
^~~~~~
175458.c:102:23: warning: incompatible implicit declaration of built-in function ‘malloc’
175458.c:102:23: note: include ‘<stdlib.h>’ or provide a declaration of ‘malloc’
175458.c:102:39: warning: conversion to ‘long unsigned int’ from ‘int’ may change the sign of the result [-Wsign-conversion]
char *arr=(char *)malloc(arr_size * sizeof(char));
^
175458.c:128:5: warning: implicit declaration of function ‘free’ [-Wimplicit-function-declaration]
free(arr);
^~~~
175458.c:128:5: warning: incompatible implicit declaration of built-in function ‘free’
175458.c:128:5: note: include ‘<stdlib.h>’ or provide a declaration of ‘free’


# Use whitespace and meaningful names

Dense code with single-letter variable names is hard to read. Use meaningful names; the few exceptions can be where a variable has sufficiently small scope (within ten lines or so).

Use whitespace to separate logical parts of the program. Typically, use a blank line or two between functions, and a blank line between sections within a function. Space around operators and names can also be helpful.

# Choose your types carefully

The problem says that inputs may be as large as a million. Standard int is guaranteed to be able to represent the range -32768 to +32767, which is not enough. Instead of assuming that int is 21 bits or more, it's worth verifying (and we don't allow negative values, so let's use unsigned types):

#include <limits.h>
#if UINT_MAX < 1000000
typedef unsigned long Integer;
#define SCN_FMT "%lu"
#define PRI_FMT "%lu"
#else
typedef unsigned int Integer;
#define SCN_FMT "%u"
#define PRI_FMT "%u"
#endif


Alternatively, we could always use long unsigned int, which must be able to represent our maximum value.

If we include <stdint.h>, then we can use uint_fast32_t, which may be our best choice:

#include <stdint.h>
#include <inttypes.h>
typedef uint_fast32_t Integer;
#define SCN_FMT "%" SCNuFAST32
#define PRI_FMT "%" PRIuFAST32


# Use a simpler GCD implementation

Reducing a fraction to its lowest terms is much more simply expressed as

Integer gcd(Integer a, Integer b)
{
/* Recursive implementation of Euclid's algorithm */
return b ? a : gcd(b, a % b);
}


Although a well-implemented binary GCD may be 20% faster than the Euclidean method, this isn't the performance-critical part of the code (and a good compiler will optimise it well, including transformation of the recursive tail-call to iterative form), so why not just write it clearly?

# Split the long query method

Instead of one huge function, we can factor out the counting and the printing, and we can avoid duplicating the even and odd counting (when we know how many even elements we have, and the total count, then there are total-even odd elements).

void print_reduced_fraction(Integer numerator, Integer denominator)
{
if (numerator == 0) {
printf("0\n");
} else if (numerator == denominator) {
printf("1\n");
} else {
Integer divisor = 1;gcd(numerator, denominator);
printf(PRI_FMT " " PRI_FMT "\n",
numerator/divisor, denominator/divisor);
}
}

Integer count_odd(const unsigned char *p, const unsigned char *end)
{
Integer n = 0;
/* N.B. end is INCLUSIVE */
while (p <= end)
n += *p++;
return n;
}

void query(const unsigned char *arr, int qtype, Integer l, Integer r, char v)
{
if (qtype == 2 && v) {
for (unsigned char *p = arr+l;  p <= arr+r;  ++p)
*p ^= 1;
return;
}

Integer total = r + 1 - l;
Integer odd = count_odd(arr+l, arr+r);
Integer even = total - odd;

print_reduced_fraction(qtype ? odd : even, total);
}


Now the qtype == 2 test is really switching between completely different code paths - well worth separating into two functions.

# Check return values from library calls

scanf() and malloc() can both fail - we can't reasonably continue if they do. printf() could fail, but we might choose to ignore that and continue regardless.

int die(const char *message)
{
fprintf(stderr, message);
return EXIT_FAILURE;
}

int main()
{
size_t tests_remaining;

if (scanf("%zu", &tests_remaining) != 1)
return die("Failed to read testcase count!\n");

while (tests_remaining--) {
size_t array_size;
int queries_remaining;
if (scanf("%zu%d", &array_size, &queries_remaining) != 2)
return die("Failed to read array size and query count!\n");

unsigned char *array = malloc(array_size * sizeof *array);
if (!array)
return die("Failed to allocate memory");

for(size_t i = 0;  i < array_size;  ++i) {
int x;
if (scanf("%d", &x) != 1)
return die("Failed to read array value");
array[i] = x & 1;
}

while(queries_remaining--) {
int query_type;
Integer left, right;
if (scanf("%i" SCN_FMT SCN_FMT, &query_type, &left, &right) != 3)
return die("Failed to read ");

/* left and right are 1-based, so subtract to index the array correctly */
unsigned char *first = array + --left;
unsigned char *last = array + --right;

switch (query_type) {
case 0:
case 1:
{
Integer total = right + 1 - left;
Integer odd = count_odd(first, last);
Integer even = total - odd;

print_reduced_fraction(query_type ? odd : even, total);
}
break;

case 2:
{
int addend;
if (scanf("%d",&addend) != 1)
return die("Failed to read update value\n");
if (addend & 1) {
/* invert values in range, inclusive */
while (first <= last)
*first++ ^= 1;
}
}
break;

default:
return die("Invalid query type\n");
}
}

free(array);
}
}


# Consider an alternative representation

Instead of accessing every element in the range of a count, it may be faster to store an array of Integer (or perhaps uint_least32_t) containing the running sum of odd elements. Then the search operations require just two accesses and a single subtraction.

This representation does likely increase the storage cost of the implementation (with concomitant effects on cache misses, etc). That's likely to have an impact on update operations (query type 2), but is probably worth trying.

It could have a big impact on updates; one mitigation would be to keep note of updates (only those with odd summand, obviously) in a separate structure (of non-overlapping ranges), and use them to apply corrections to the raw counts from the unmodified input array.

The good news is that having refactored into individual methods, most of them are unaffected by the change in representation, so it was well worth doing that first!