Để tìm xác suất chẵn lẻ của các số, tức là chẵn hay lẻ và cho các phạm vi đã cho. Đối với mỗi truy vấn, chúng ta cần in p và q đại diện cho xác suất bằng p / q, chẳng hạn.
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 Trong bài toán này, chúng ta sẽ duy trì hai mảng chứa số lượng các số lẻ và số chẵn có mặt cho đến chỉ số đó. Điều này đơn giản hóa các vấn đề của chúng tôi và bây giờ chúng tôi cần in số lượng của chúng và số phần tử có trong phạm vi đó.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi duy trì hai mảng. Chúng chứa số lượng các số chẵn và lẻ được tìm thấy cho đến chỉ mục thứ i và giải quyết vấn đề này như các bài toán về tổng tiền tố.
Ví dụ
#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'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;
} Đầu ra
0 3 4
Giải thích về Quy tắc trên
Trong cách tiếp cận trên, chúng tôi đếm số lượng các số chẵn và lẻ được tìm thấy trong chỉ mục thứ i bằng cách duy trì hai mảng. Bây giờ chúng ta cần tìm số lượng các số chẵn hoặc lẻ có trong phạm vi đã cho và in ra số đó và in ra tổng số phần tử có mặt.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết các Truy vấn về xác suất của các số chẵn hoặc lẻ trong các phạm vi nhất định. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.