You are not logged in.
Pages: 1
We have a vector of numbers and we want to know how many pairs have an
even product and how many pairs have an odd product.
Example: the vector of numbers is 1,3,4,7,10. We can form 25 pairs:
| ?x2 ?x3 ?x4 ?x7 ?x10
-----+----------------------------------------------
2x? | 2x2= 4 2x3= 6 2x4= 8 2x7=14 2x10= 20
3x? | 3x2= 6 3x3= 9 3x4=12 3x7=21 3x10= 30
4x? | 4x2= 8 4x3=12 4x4=16 4x7=28 4x10= 40
7x? | 7x2=14 7x3=21 7x4=28 7x7=49 7x10= 70
10x? | 10x2=20 10x3=30 10x4=40 10x7=70 10x10=100We see that there are only 4 odd products:
9 (=3x3), 21 (=3x7), 21 (7x3), 49 (7x7).Do we have to check all 25 (5^2) pairs to find this result?
No!
If we multiply an even number with something, the product is even.
Only if we multiply two odd numbers, the product is odd.
So, let's annotate the above table with EVEN and ODD
| ?x2 ?x3 ?x4 ?x7 ?x10
| EVEN ODD EVEN ODD EVEN
----------+--------------------------------------------------
2x? EVEN | 2x2= 4 2x3= 6 2x4= 8 2x7=14 2x10= 20
3x? ODD | 3x2= 6 3x3= 9(*) 3x4=12 3x7=21(*) 3x10= 30
4x? EVEN | 4x2= 8 4x3=12 4x4=16 4x7=28 4x10= 40
7x? ODD | 7x2=14 7x3=21(*) 7x4=28 7x7=49(*) 7x10= 70
10x? EVEN | 10x2=20 10x3=30 10x4=40 10x7=70 10x10=100and this confirms that only the 4 products formed by multipling two
ODD numbers (they are marked with (*) in the table) are odd. The other
pairs (even x even, even x odd, odd x even) are all even.
This means that
e= 0;
o= 0;
for(i=0; i<size; ++i)
{
if( even(vec[i]) )
{
e++;
}
else
{
o++;
}
}
ep= e*e + e*o + o*e
op= o*ogives the correct result, in O(n) as opposed to the O(n^2) of the original
algorithm.
Maarten Pennings
(yes, I'm the author of MatheMagie)
(check p51 at http://www.fampennings.nl/maarten/boeken/MatheMagie.pdf)
(yes, the book has a serious typo in this puzzle)
Pages: 1