Math Is Fun Forum

Valmont

Member

Registered: 2005-08-27

Posts: 2

[algorithm] products of even/odd pair combinations help

I need help on the following puzzle. I'll tell you the requirements then the story behind it.

Requirement:
find the amount of even and odd products from a vector with n elements in it. Or more specific:
ep = | {(i,j) :: 0 <= i < n AND 0 <= j < n AND even(Numbers[ i ] * Numbers[ j ]) |
op = | {(i,j) :: 0 <= i < n AND 0 <= j < n AND odd(Numbers[ i ] * Numbers[ j ]) |

Make an algorithm in some pseudo/imper coding language.

The Story

A collegue of mine sent me two algorithms, one algorithm takes too long (O(n^n) ) and one with complexity O(n). He claimed that the algorithm met the requirements as posted above. He was wrong and a student of found out (I never checked it).
I"ll give you the code:

#include <iostream>
#include <cstdlib>

void odd_even_pairs(const int* vec, std::size_t size, unsigned& ep, unsigned& op);
void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op);
bool even(int num);

static const int Numbers[] = {12, 4, 6, 3, 7, 9, 10 , 44, 63, 63, 23, 34, 36, 
  346, 43, 61, 56, 264, 2463, 25, 2544, 14, 14, 11, 99, 345, -5, -34, -24};

int main()
{
  unsigned ep(0), op(0);
  std::size_t size(0);
  size = sizeof Numbers / sizeof *Numbers;
  
  odd_even_pairs(Numbers, size, ep, op);
  std::cout<<"Even pairs: " << ep << std::endl;
  std::cout<<"Odd pairs: " << op <<std::endl;
  
  return 0;
}

//------------------------------------

bool even(int num)
{
  return ((num % 2) == 0);
}

//-------------------------------------

void odd_even_pairs(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{  
  for(std::size_t i = 0; i < size; ++i)
  {
    for(std::size_t j = 0; j < size; ++j)
    {
      if( even(vec[i]) == even(vec[j]) )
      {
        ++ep;
      }
      else
      {
        ++op;
      }
    }
  }  
}

//-------------------------------------

void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{
   // TO DO BY STUDENT  
}

Obviously there is a flaw in his code because multiplication by an ODD number gives you an EVEN product if the other half of the pair is EVEN.

When I asked him what made him think this algorithm was correct, he answered he didn't check either: he got it from a (Dutch) book: MatheMagie by Maarten Pennings.
So there you have it. One big mess.

My question:

Does anyone have an efficient  forumula to calculate where the postcondition as posted in blue is met?

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,713

Re: [algorithm] products of even/odd pair combinations help

In other words, if presented with a list of numbers (say: 3,4,7,10), find out how many even pairs there are and how many odd.

In that case:

3×4=12 Even
3×7=21 Odd
3×10=30 Even
4×7=28 Even
4×10=40 Even
7×10=70 Even

So the answer is 1 Odd and 5 Even

I wonder if it would work to:
a) calculate the total number of pairs (my memory says it is n(n-1)/2 but I may be wrong)
b) count the odds, then calculate the total number of odd pairs (same formula)

Because the only odd products come from two odd factors, all others will be even.

(this was a quick post without much thought, I may have to come back and amend it)

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Valmont

Member

Registered: 2005-08-27

Posts: 2

Re: [algorithm] products of even/odd pair combinations help

We need all the permutations: both "i" and "j" need to be of range { 1 <= "i/j" <= n }
but in my first post the lowest index was 0 and the highest index of the element was n-1 instead of "n". This is C++ specific because the index of the first element starts at 0. So the last one is n-1.

If the vector is: {2,3,5}
then we have these pairs:
2*2 = 4
2*3 = 6
2*5 = 10
3*2 = 6
3*3 = 9
3*5 = 15
5*2 = 10
5*3 = 15
5*5 = 25

However, you gave me the right hint. I've solved it.
The big hint is n^2. That's it.

Thanks for your "quick thought" . I was way too angry for a moment to think on my own you see :).

Last edited by Valmont (2005-08-27 21:38:58)

maartenpennings

Member

Registered: 2007-01-12

Posts: 1

Re: [algorithm] products of even/odd pair combinations help

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=100

We 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=100

and 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*o

gives 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)