March 18th, 2002, 01:15 PM

Puzzle: Find the error in this algorithm.
I figure that this forum could use a puzzle or two, once in a while. So here's my first effort  basically the idea is to find if there is a flaw in the logic below:
Algorithm to determine odd or even number:
1. Perform a modulo divide operation by 2 on the number to get the reminder.
2. If the reminder is 1, the number is odd, otherwise the number is even.
Expressed in C, the code would look something like this:
Code:
#include <stdio.h>
void odd_even(int x) {
if ((x % 2) == 1)
printf("%d is odd\n", x);
else
printf("%d is even\n", x);
}
int main() {
odd_even(2);
odd_even(1);
}
So, is there anything wrong with this algorithm. Post your replies here.
March 18th, 2002, 02:05 PM

Well, first of all this could done much easier using a bitwise AND with 1, which would also fix the flaw in the algorithm, namely that 1 (or any odd negative number for that matter) will be marked as even because 1%2 = 1.

Regards
André Nęss
Puritanism: The haunting fear that someone, somewhere may be having fun
March 18th, 2002, 03:35 PM

Congratulations Andaness, you found the right answer! I didn't think the puzzle would be cracked so quickly . One other way to fix it would be to reverse the check as in:
Code:
if (number modulo 2) = 0 then
it is an even number
else
it is an odd number
This will also work with negative numbers.
The bitwise AND is the more efficient way to determine if this is an odd or even number, but the modulo method was discussed for the purposes of this puzzle. (NOTE: For all the new readers in this forum, the bitwise AND algorithm was discussed earlier in Quick algorithm to determine odd/even numbers Check out the difference in the size of the code using the modulo method and the bitwise method and you'll clearly see where the efficiency comes from.)