Count the number of even/odd results after performing a series of calculation on a range of numbers.
Given that: Each layer of calculation have two numbers (say a and b) associated with it. For each input x, y = ax + b is calculated. The result of layer i, i.e y, becomes input for layer i+1.
The range is given by the user, for each element of which the calculation is to be performed.
Required Inputs:
Numbers of layers: n.
n lines containing values of a and b for each layer.
The range of numbers on which operation is to be performed: [min, max].
Basic Approach:
The most basic approach will be to store the values of a and b in an array and calculate the final result for each number in the specified range. If the result is even, count of even is incremented. Otherwise, count of odd is incremented.
Better Approach:
The approach used here is the basic concept that product of two numbers is even if any one of the numbers is even, otherwise odd, and the sum of two numbers is even only if both the numbers are even.
Explanation:
At layer 1, the calculation is: y1 = a1x + b1
At layer 2, it is: y2 = a2y1 + b2
=> y2 = a2a1x + a2b1 + b2
At layer 3, it is: y3 = a3y2 + b3
=> y3 = a3a2a1x + a3a2b1 + a3b2 + b3
.
.
.
At level i, it is: yi = aiyi-1 + bi
.
.
.
Here, we can see that at each layer, a number is multiplied with x, and another constant is added to the product. The task is to check for the result to be even or odd.
At the last level of calculation, we ultimately have to check that if a1a2a3…an is even/odd, and a2a3…anb1 + a3a4…anb2 + … + bn is even/odd.
Checking if a1a2a3…an is even/odd: If any ai is even, the product will always be even, otherwise odd.
Checking if a2a3…anb1 + a3a4…anb2 + … + bn is even/odd:
| a2a3…ai-1b1 + a3a4…ai-1b2 + … + bi-1 | ai | bi | a2a3…aib1 + a3a4…aib2 + … + bi |
|---|---|---|---|
| odd | odd | odd | even |
| odd | odd | even | odd |
| odd | even | odd | odd |
| odd | even | even | even |
| even | odd | odd | odd |
| even | odd | even | even |
| even | even | odd | odd |
| even | even | even | even |
Now, a similar table is made for the final calculation, y = ax + b
| x | a | b | y |
|---|---|---|---|
| odd | odd | odd | even |
| odd | odd | even | odd |
| odd | even | odd | odd |
| odd | even | even | even |
| even | odd | odd | odd |
| even | odd | even | even |
| even | even | odd | odd |
| even | even | even | even |
Now, instead of traversing through all the number in the range [min, max], we divide it into two parts, whether the number in the range is even or odd as all the even inputs have the same result, and all the odd inputs have the same result. So we check for one case and multiply it by the number of even and odd in the range.
Examples:
Input: 4 5 1000000 2 7 3 10 1 5 6 2 Output: 999996 0
Explanation:
The first line of input gives us the number of layers, n = 4, and the range of numbers in which we have to check as [5, 1000000].
Now, the next n lines give values of a and b for each layer.
At layer 1: y1 = 2x + 7
At layer 2: y2 = 3y1 + 10 = 6x + 31
At layer 3: y3 = y2 + 5 = 6x + 36
At layer 4: y4 = 6y3 + 2 = 36x + 1296
The above calculation is carried out, and the coefficient of x at last layer is checked. If it is even, then aeven is true, else false. If the constant is even, then beven is true, otherwise false.
The coefficient of x is even of any one value of a is even in any one layer. The constant term after the last layer if executed is checked with the help of value of beven, and current a and b. With the help of the table given above (first one), the constant at each layer is tested and value of beven is updated accordingly.
Then, assuming x is even, the value of even and odd is initialized. If x is even, then ax will always be even, regardless of a. Hence, depending on the value of the constant term, the result will be even or odd. If the constant is even, then the result is even, hence even is initialized by the number of even in the given range ( max/2 – (min-1)/2 ) and odd is initialized by zero. If constant is odd, then the result is odd, hence odd is initialized by the number of even in the given range ( max/2 – (min-1)/2 ) and even is initialized by zero.
Then, assuming x is odd, the value of even and odd is updated. If a is odd, ax is odd. If a is even, ax is even. If ax and constant, both are odd or ax and constant, both are even, then the result is even, hence even is incremented by the number of odd in the given range ( max – min + 1 – number of even). If ax is even and constant is odd or ax is odd and constant is odd, then the result is odd, hence the number of odd is incremented by the number of odd in the given range ( max – min + 1 – number of even).
Input: 1 4 60 1 2 Output: 29 28
Expalantion: It has only one layer and the range given is [4, 60].
y = x + 2
Here, the coefficient of x is odd, so aeven is false and the constant is even, so beven is odd. Rest of the procedure is same as in the previous example.
Implementation:
#include <iostream>
using namespace std;
/* Function which takes the required input and
prints the count of even and odd outputs.
*/
void count_even_odd() {
int n, min, max, a, b, even, odd;
bool beven = true, aeven = false;
// If constant at layer i is even, beven is true,
// otherwise false. If the coefficient of x at
// layer i is even, aeven is true, otherwise false.
cin >> n >> min >> max;
while (n--) {
cin >> a >> b;
// If any of the coefficients at any layer is found
// to be even, then the product of all the
// coefficients will always be even.
if (!(aeven || (a & 1))) {
aeven = true;
}
// Checking whether the constant added after all
// layers is even or odd.
if (beven) {
if (b & 1) {
beven = false;
}
} else if (!(a & 1)) {
if (!(b & 1)) {
beven = true;
}
} else {
if (b & 1) {
beven = true;
}
}
}
// Counting the number of even and odd.
// Assuming input x is even.
even = (max / 2) - ((min - 1) / 2);
odd = max - min + 1 - even;
// Assuming input x is odd.
if (!(beven ^ aeven)) {
even += odd;
}
// Displaying the counts.
cout << even << " " << odd << endl;
}
/* Driver function for count_even_odd().
*/
int main() {
count_even_odd();
return 0;
}