Pascal - odd and even number

Question

I want to make an algorithm which return whether is ginen number odd or even without using built-in functions like mod, div, odd(). Only solution that I made up is following, but it isn't much robust and only for numbers higher then 0

Var
  n: integer;

begin
  ReadLn(n);
  While (n not in [1, 0]) do
    n:=n-2;
  if n = 1 then
    WriteLn('odd')
  else
    WriteLn('even');
end.

Thank you for your help.

Answer 1

well, to make it work with negative numbers you can just check if the number is negative and if it is, multiply with -1 (or just use abs).

The only issue with your algorithm is efficiency; runs in o(n). Some other ideas:

• Checking the least significant bit (which is probably the last)
• Integer division with 2 (could be done by dividing and trunc), the multiply the result with 2 and check if it's the same number

• Check if the last digit is 0,2,4,6,8 (really good if the number is given as a string/array) In each step of your algorithm increase the subtracted number till you hit negative then reverse the process. For example, let's say we want to check 64:

  1. 64 - 2 = 62, it's >0 but not 0 or 1
  2. 63 - 4 = 58, >0, not 0/1
  3. 50 - 8 = 42, >0, not 0/1
  4. 42 -16 = 26, >0, not 0/1
  5. 26 -32 = -6, <0 => reverse
  6. 26 -16 = 10, >0, not 0/1
  7. 10 - 8 = 2, >0, not 0/1
  8. 2 - 4 = -2, <0 => reverse
  9. 2 - 2 = 0, =0 => even

So 10 steps instead of 63.
Note that after the first reverse, we decrease the subtracted number on each step because we know that it's less than 2x the number we subtract. Of course, you can create a ton of variations, some of them which are probably more efficient.