We have given an array of integer, q number of queries. Where each query contains three integers, which defines a type of query. This means if we have given 0 it means we have to find the probability of choosing an odd number in the given range. Where the range is defined as a starting point and an ending point. Within this particular range of any type of particular query. You have to find the solution for each query. Each query will be in the form of
T S E: if you have given T=0, it means you have to find the probability of choosing an even number in the given range (S: Starting Point, E: Ending Point) in the given array A.
T S E: if you have given T=1, Then it means you have to find the probability of choosing an odd number in the given range (S: Starting Point, E: Ending Point) in the given array A.
Table of Contents
Example
Input:
array[]={2, 3, 4, 5, 6}
Query 1: 1 1 3
Query 1: 0 1 4
Output:
1/3
1/2
Explanation:
we have given T = 1, in a query, means we have to find the probability of choosing an odd number in the range 1 and 3 inclusively.
we have given T = 0, in a query, means we have to find the probability of choosing an even number in the range 1 and 4 inclusively.
Algorithm
- Create two arrays for odd numbers and even numbers, of the size the same as a given array. Initialize the first element of both of the array to 0.
- Traverse the array and check if the number is odd then fill the value of oddNumber array we created to the number of odd[i] + 1 and into the even array we created to the number even[i] and same if even number found, store the odd number into the current odd evenNumber array, and oddNumber array to the oddNumber array.
- Traverse till the query number of times, and store the difference of right, left and 1.
- Check if we have to choose even number or odd number to find the probability, if an odd number, then store the value in probab as the difference of oddNumber[right] and oddNumber[left – 1].
- Else store the value in probab as the difference of evenNumber[right] and evenNumber[left – 1].
- Check if the probab is less than or equal to 0, then print 0. Else if it is equal to temp, then print 1. Else find the total number of favors that can be counted.
- Print the value probab and that number of favours.
Explanation
We are going to create two arrays one for odd number and one for even number to store. Now, we are going to traverse the array and find if the array element is odd or even if it is odd. We will be storing the even number to the oddNumber array. And the evenNumber previous value to current value of evenNumber, same is to be followed if the number is even. Then store the odd value to evenNumber array and oddNumber array’s previous value to the current oddNumber’s current value. All of this is to create and fill an array with numbers in created arrays respectively.
Fetch the type of the query, left and the right points as a range, get the difference of them. We will find the given query is of which type. If it is greater than 1, then we have to chose an odd number to find out the probability of choosing an even number. Else we will find the probability of even number within a range. If it is odd, then we will get the difference of oddNumber array we created and same with the even number probability, the difference of evenNumber. We will store the difference in probab, and if probab is less than or equal to 0, we will print 0, else if it is probab is equal to k, print 1. Else we need to find the total number of favours. And finally, print the value probab and favours.
Implementation
C++ program for Queries on Probability of Even or Odd Number in given Ranges
#include<iostream>
using namespace std;
#define C 3
int getDivisor(int a, int b)
{
if (a == 0 || b == 0)
return 0;
if (a == b)
return a;
if (a > b)
return getDivisor(a - b, b);
return getDivisor(a, b - a);
}
void solveQuery(int arr[], int n, int Q,int query[][C])
{
int evenNumber[n + 1];
int oddNumber[n + 1];
evenNumber[0] = oddNumber[0] = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] & 1)
{
oddNumber[i + 1] = oddNumber[i] + 1;
evenNumber[i + 1] = evenNumber[i];
}
else
{
evenNumber[i + 1] = evenNumber[i] + 1;
oddNumber[i + 1] = oddNumber[i];
}
}
for (int i = 0; i < Q; i++)
{
int right = query[i][2];
int left = query[i][1];
int T = query[i][0];
int dif = right - left + 1;
int probab;
if (T)
probab = oddNumber[right] - oddNumber[left - 1];
else
probab = evenNumber[right] - evenNumber[left - 1];
if (!probab)
cout << "0" << endl;
else if (probab == dif)
cout << "1" << endl;
else
{
int div = getDivisor(probab, dif);
cout << probab / div << "/" << dif / div << endl;
}
}
}
int main()
{
int arr[] = { 2,3,4,5,6};
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 2;
int query[Q][C] = { { 1, 1, 3 },
{ 0, 1, 4 }
};
solveQuery(arr, n, Q, query);
return 0;
}
1/3 1/2
Java program for Queries on Probability of Even or Odd Number in given Ranges
public class QueryProbability
{
static int getDivisor(int a, int b)
{
if (a == 0 || b == 0)
return 0;
if (a == b)
return a;
if (a > b)
return getDivisor(a - b, b);
return getDivisor(a, b - a);
}
static void solveQuery(int []arr, int n, int Q, int [][]query)
{
int []evenNumber = new int[n + 1];
int []oddNumber = new int[n + 1];
evenNumber[0] = oddNumber[0] = 0;
for (int i = 0; i < n; i++)
{
if ((arr[i] & 1) > 0)
{
oddNumber[i + 1] = oddNumber[i] + 1;
evenNumber[i + 1] = evenNumber[i];
}
else
{
evenNumber[i + 1] = evenNumber[i] + 1;
oddNumber[i + 1] = oddNumber[i];
}
}
for (int i = 0; i < Q; i++)
{
int right = query[i][2];
int left = query[i][1];
int T = query[i][0];
int dif = right - left + 1;
int probab;
if (T > 0)
probab = oddNumber[right] - oddNumber[left - 1];
else
probab = evenNumber[right] - evenNumber[left - 1];
if (probab <= 0)
System.out.println("0");
else if (probab == dif)
System.out.println("1");
else
{
int div = getDivisor(probab, dif);
System.out.println(probab / div + "/" +dif / div);
}
}
}
static public void main (String[] args)
{
int []arr = { 2, 3, 4, 5, 6 };
int n = arr.length;
int Q = 2;
int [][]query = { { 1, 1, 3 },
{ 0, 1, 4 }
};
solveQuery(arr, n, Q, query);
}
}
1/3 1/2
Complexity Analysis for Queries on Probability of Even or Odd Number in given Ranges
Time Complexity
O(q*n) where “q” is the number of queries and “n” is the number of elements in the array
Space Complexity
O(n) where “n” is the number of elements in the array.