[puzzle] Improve my bad code.

[Valmont]

Assume a mathematical vector (which is just a 1-D matrix) containing n numbers in Z .
For C++ this means that the range of the vector is: Numbers [0...n) .

The task is to find all possible odd and even product pairs (all permitations, not combinations).
Or more formally:

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


I'll give you the full working code below which does that precisely. However, with the type of mathematical problem as stated above my code is totally unacceptable! This direct method is called: canonical form.

Your task:
Improve my code so the run-time complexity decreases from a horrible N^2 to N.

Motivation:
Here lies the foundation of classical programming. These kind of problems are for any coder to solve if you take yourself serious.

#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_fast(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] * 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
}

[Feis]

Ok, dont try to compile, as my compiler is messed up and this probly has a few errors

The basis of the program is this: YOU DONT HAVE TO KNOW WHETHER ITS EVEN!


Yes, I know that sounds weird, but look:

you take a number, lets say 5 for example. if you add the next number, 6, the sum is ALWAYS odd. this is true for all whole numbers. adding 2 to this next number keeps the number odd. so 5+8=13, 5+10=15, etc.

The same goes for even. still using 5, 5+7=12, always even. Adding 2 to the second number insures tha the sum is always even. so here it is, please excuse any coding errors, but I think that you'll get the gist of the concept.

#include<iostream>
int n = 999;       //whatever n is
using std::cout;

int Numbers[n] = (1,2,3)          //so on and so forth

int main()
{
    int even=0, odd=0;
    
    for(int i=0, i>n, i++;)
    {
            
               for(int k = i+2, k>n, k+=2;)
                 {
                         even++;
                 }
                 for(int l=i+1, l>n, l+=2;)
                 {
                         odd++;
                 }
}

cout << "The # of even pairs are:" << even;
cout << "The # of odd pairs are:" << odd;


return 0;
}

heres to hoping I didnt make a blatant error in my logic

[Valmont]

You've got more wrong then only your logic.

[smckittr]

Valmont,
are you looking for pairs like 33 or 22 where both digits are the same?
Scott

[redhead]

odd and even pairs, like [2,6] ; [17,9]

[Valmont]

Like redhead's example. Run and debug my code to seee what it does. Altough it should be pretty obvious what it does from here.

[redhead]

Run and debug my code to seee what it does.

To make this clear, here is a small example:

const int numbers[] = {1, 2, 4, 3, 6, 5, 14};

There will be 6 odd pairs ({1,3};{3,1};{1,5}{5,1};{3,5};{5,3}) or 3! since theres 3 odd numbers in the vector.
(Oops was that too much of a hint...)
Anyway I think people get the idear, the task here is to make a way of looping through the array in O(N) time instead of the O(N^2) time which Valmonts solution does.

[teknomage1]

I have a question, Val. In the current code, won't pairs that are both even or both odd get added to ep while pairs that that are one even and one odd be added to op? Is it supposed to be tallied this way?

[Valmont]

I have a question, Val. In the current code, won't pairs that are both even or both odd get added to ep while pairs that that are one even and one odd be added to op? Is it supposed to be tallied this way?

YOU ARE RIGHT! I MADE A MISTAKE.
The program does what it should do but I explained it wrong!!!! OMG.

We want to know the amount of EVEN or ODD PRODUCT pairs.
So basically:
ep = even(Numbers[i] * Numbers[j])
op = odd(Numbers[i] * Numbers[j])

Thanks for pointing out this huge flaw in the postcondition. However the code remains correct. I have updated it in my original post.
Well done!

[Valmont]

You know what? Nevermind at all because this postcondition isn't correct either. I think we found a serious error somewhere. I need to figure out what is going on. It boils down to kicking the butt of a colleague...

edit
Ok I figured it out my self. See the first post in this thread. It's updated.
My colleage got this from a book:
MatheMagie (author Maarten Pennings)
But he never checked it. Nor did I. Both the algorithms in the book were wrong.

Anyway, continue solving this simple puzzle. Just reread the first post and the code.

[Locutus]

If I'm understanding the problem correctly we're looking for the number of pairs for which the product is even/odd. A number is even if it has 2 as one of it's factors and odd if it hasn't.

So:
even*even=even
even*odd=even
odd*odd=odd.

op then becomes ((num_o * num_o) - num_o).
The total number of pairs is ((size * size) - size), so ep becomes ((size * size) - size) - op.

void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{
	op = 0;		//Being able to call the function more than once, for whatever reason, is probably nice.
	std::size_t i;
	
	for (i = 0; i < size; ++i)
	{
		if (!even(vec[i])) ++op;
	}

	op = (op*op) - op;
	ep = ((size * size) - size) - op;
}

I should probably test the code before posting, but m3h

[Valmont]

- The total number of all possible pairs you guessed wrong.
- The algorithm for odd/even products is wrong too but that is closely related on your guesstimation on total possible pairs.
- Resetting variables in that function for re-use is inappropriate since that is not the responsibility of that function. Nor was that part of the task.
However, setting that variable to "0" for reasons of correctness would have been correct. I should have done that to make sure the precondition is right. In your (and mine) case you should have set "ep" to 0 as well for this very reason.

You forgot that both "i" and "j" INCLUDE index "0". So you need to start with Numbers[0]*Numbers[0]. If you did that right then your algorithm would have been correct.

Also this:

std::size_t i;
	
for (i = 0; i < size; ++i)

Keep "i" in the scope of the for-loop only. Now it's scope has been extended to the function for no valid reason.

All this the correct code:

void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{
  ep =0; op =0; //Guarantee correct precondition.
  for(std::size_t i = 0; i < size; ++i)
  {
    if( !even(vec[i]))
    {
      ++op;      
    }
  }
  op *= op;
  ep = (unsigned)(size * size) - op;
}

I think you did well.

[Locutus]

Originally Posted by Valmont

- The total number of all possible pairs you guessed wrong.
- The algorithm for odd/even products is wrong too but that is closely related on your guesstimation on total possible pairs.

I assumed (wrongly?) you shouldn't count pairs of elements with themselves.

Originally Posted by Valmont

- Resetting variables in that function for re-use is inappropriate since that is not the responsibility of that function. Nor was that part of the task.
However, setting that variable to "0" for reasons of correctness would have been correct. I should have done that to make sure the precondition is right. In your (and mine) case you should have set "ep" to 0 for this very reason.

It's not so much about re-use as it is about initialising variables before you modify/read from them. It all comes down to the same thing, really, but I guess I should have formulated it differently.
I didn't set ep to 0 because you never read from it.

Originally Posted by Valmont

Also this:

std::size_t i;
	
for (i = 0; i < size; ++i)

Keep "i" in the scope of the for-loop only. Now it's scope has been extended to the function for no valid reason.

I actually knew that
I kinda got used to doing it this way for clarity / compiler portability, since certain dodgy compilers (like MSVC6) extend the scope of "i" to the entire function even if you do declare it within the for-loop.

[Valmont]

you shouldn't count pairs of elements with themselves.

The postcondition was set (in blue). We don't know what the reason is. So don't change it.

I didn't set ep to 0 because you never read from it.

Agreed!

since certain dodgy compilers (like MSVC6) extend the scope of "i" to the entire function even if you do declare it within the for-loop.

Good point but you can circumvent this problem whilst keeping the portability by explicity scoping:

void my_function()
{
   {//scope start
   for(int i = 0;; i++)
   {
   }
   }//scope end;
}

[Locutus]

Originally Posted by Valmont

The postcondition was set (in blue). We don't know what the reason is. So don't change it.

True. Nevertheless, this line is slightly misleading

Originally Posted by Valmont

The task is to find all possible odd and even product pairs (all permitations, not combinations).

Informal explanations are tricky. That's why I added the formal definition.