숫자 패리티의 확률, 즉, 짝수인지 홀수인지, 그리고 주어진 범위에 대해 찾습니다. 각 쿼리에 대해 예를 들어 p / q로 확률을 나타내는 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 이 문제에서는 해당 인덱스까지 존재하는 홀수 및 짝수의 개수를 포함하는 두 개의 배열을 유지합니다. 이렇게 하면 문제가 간단해지며 이제 해당 범위에 있는 요소 수와 요소 수를 인쇄해야 합니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 두 개의 배열을 유지 관리합니다. i번째 인덱스까지 발견된 짝수와 홀수의 개수를 포함하고 있으며 이 문제를 접두사 합 문제와 같이 해결합니다.
예
#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;
} 출력
0 3 4
위 코드 설명
위의 접근 방식에서 우리는 두 개의 배열을 유지하여 i번째 인덱스에서 찾은 짝수 및 홀수의 개수를 계산합니다. 이제 우리는 주어진 범위에 존재하는 짝수 또는 홀수의 수를 찾아 그 수를 출력하고 존재하는 요소의 총 수를 출력해야 합니다.
결론
이 튜토리얼에서는 주어진 범위에서 짝수 또는 홀수의 확률에 대한 쿼리를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.