C++ Query the probability of even or odd numbers in a given range

Find the probability of parity of a number within a given range, that is, whether it is an even number or an odd number. For each query, we need to print p and q, e.g. denote the probability by p / q.

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

In this problem, we will maintain two arrays containing odd and even amounts respectively up to that index. This simplifies our problem, now we need to print their number and the number of elements present in the range.

Solution method

In this method, we maintain two arrays. They contain the number of even and odd numbers found up to the i-th index, and solve the problem like a prefix sum problem.

Example

#include <bits/stdc++.h>
using namespace std;
void solve(int arr[], int n, int Q,int query[][3]){
    int even[n + 1]; // our array for counting the number of evens find till ith index
    int odd[n + 1]; // our array for counting the number of odds find till ith index
    even[0] = 0; odd[0] = 0; // as we are doing 1 based indexing so we just set 0th index of both arrays to 0
    for (int i = 0; i < n; i++) {
        if (arr[i] & 1) { // if we found odd number we increment odd
            odd[i + 1] = odd[i] + 1;
            even[i + 1] = even[i];
        }
        else { // else we increment even
            even[i + 1] = even[i] + 1;
            odd[i + 1] = odd[i];
        }
    }
    for (int i = 0; i < Q; i++) { // traversing the queries
        int r = query[i][2]; // right range
        int l = query[i][1]; // left range
        int k = query[i][0]; // type of query
        int q = r - l + 1; // number of elements in the given range
        int p;
        if (k) // k is the type of query and we are finding the
            //number of elements with same parity in the given range
            p = odd[r] - odd[l - 1];
        else
            p = even[r] - even[l - 1];
        if (!p) // if p is zero we simply print 0
            cout << "0\n";
        else if (p == q) // if p == q we print 1
            cout << "1\n";
        else {
            int g = __gcd(p, q);
            cout << p / g << " " << q / g << "\n"; // as p and shouldn&#39;t have a common gcd so we divide the gcd
        }
    }
}
int main(){
    int arr[] = { 6, 5, 2, 1, 7 }; // given array
    int n = sizeof(arr) / sizeof(int); // size of our array
    int Q = 2; // number of our queries
    int query[Q][3] = {{ 0, 2, 2 },{ 1, 2, 5 }}; // given queries
    solve(arr, n, Q, query);
    return 0;
}

Output

0
3 4

Explanation of the above code

In the above method, we calculate the found to i-th by maintaining two arrays The number of even and odd indexes. Now we need to find the number of even or odd numbers in a given range and print that number and print the total number of occurrences of elements.

Conclusion

In this tutorial, we solved the problem about the probability of an even or odd number in a given range. We also learned the C program for this problem and our complete method to solve this problem (normal method). We can write the same program in other languages ​​like C, Java, Python and others. Hope you found this tutorial helpful.

The above is the detailed content of C++ Query the probability of even or odd numbers in a given range. For more information, please follow other related articles on the PHP Chinese website!