Queries on probability of even or odd number in given ranges
Given an array A of size N, containing integers. We have to answer Q queries where each query is of the form:
 K L R : If K = 0, then you have to find the probability of choosing an even number from the segment [L, R] (both inclusive) in the array A.
 K L R : If K = 1, then you have to find the probability of choosing an odd number from the segment [L, R] (both inclusive) in the array A.
For each query print two integers p and q which represent the probability p/q. Both p and q are reduced to the minimal form.
If p is 0 print 0 or if p is equal to q print 1, otherwise print p and q alone.
Examples:
Input : N = 5, arr[] = { 6, 5, 2, 1, 7 } query 1: 0 2 2 query 2: 1 2 5 query 3: 0 1 4 Output : 0 3 4 1 2 Explanation : First query is to find probability of even element in range [2, 2]. Since range contains a single element 5 which is odd, the answer is 0. Second query is to find probability of odd element in range [2, 5]. There are 3 odd elements in range probability is 3/4. Third query is for even elements in range from 1 to 4. Since there are equal even and odd elements, probability is 2/4 which is 1/2.
The idea is to maintain two arrays, say even[] and odd[], which maintain the number of even or odd element upto index i. Now, to answer each query, we can compute result denominator q by finding number of element in the given query range. To find result numerator, we remove number of elements upto l – 1 from elements upto r.
To output the answer in minimal form, we find the GCD of p and q and output p/gcd and q/gcd. For answer 0 and 1, we will explicitly specify the conditions.
Below is C++ implementation of this approach:

// CPP program to find probability of even
// or odd elements in a given range.
#include <bits/stdc++.h>
using
namespace
std;
// Number of tuples in a query
#define C 3
// Solve each query of K L R form
void
solveQuery(
int
arr[],
int
n,
int
Q,
int
query[][C])
{
// To count number of odd and even
// number upto ith index.
int
even[n + 1];
int
odd[n + 1];
even[0] = odd[0] = 0;
// Counting number of odd and even
// integer upto index i
for
(
int
i = 0; i < n; i++) {
// If number is odd, increment the
// count of odd frequency leave
// even frequency same.
if
(arr[i] & 1) {
odd[i + 1] = odd[i] + 1;
even[i + 1] = even[i];
}
// If number is even, increment the
// count of even frequency leave odd
// frequency same.
else
{
even[i + 1] = even[i] + 1;
odd[i + 1] = odd[i];
}
}
// To solve each query
for
(
int
i = 0; i < Q; i++) {
int
r = query[i][2];
int
l = query[i][1];
int
k = query[i][0];
// Counting total number of element in
// current query
int
q = r  l + 1;
int
p;
// Counting number of odd or even element
// in current query range
if
(k)
p = odd[r]  odd[l  1];
else
p = even[r]  even[l  1];
// If frequency is 0, output 0
if
(!p)
cout <<
"0"
<< endl;
// If frequency is equal to number of
// element in current range output 1.
else
if
(p == q)
cout <<
"1"
<< endl;
// Else find the GCD of both. If yes,
// output by dividing both number by gcd
// to output the answer in reduced form.
else
{
int
g = __gcd(p, q);
cout << p / g <<
" "
<< q / g << endl;
}
}
}
// Driven Program
int
main()
{
int
arr[] = { 6, 5, 2, 1, 7 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
int
Q = 2;
int
query[Q][C] = {
{ 0, 2, 2 },
{ 1, 2, 5 }
};
solveQuery(arr, n, Q, query);
return
0;
}
Output:
0 3 4
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide