How to determine if a number is odd or even without mod -or- bitwise operations?

Question

How to determine if a number is odd or even without mod -or- bitwise operations?

This challenge is grossly inefficient, but challenges your ability to think outside the box for a creative solution.

EDIT:

Please create a function. Also, while regex is a fun response, the function should accept any valid number.

BACKGROUND: This question stems from my earliest programming days. The homework for our first day of class was to write a simple program that printed 'odd' or 'even'. Being the brat I was, I didn't read the book we had for the class where it simply showed us how to use % to determine that. I spent about a half hour pacing back in forth in my room trying to think of a way to do this and had remembered from the lecture that numbers can lose and gain precision as they are cast from one primitive type to another. Therefore, if you took the number, divided it by two and then multiplied it back didn't equal the original number, then you would know that the number was odd.

I was stunned the next day, while our instructor was evaluating our programs, that he thought that it was the most original, if inefficient, way of solving the problem.

Answer 1

In most programming languages division returns quotient for integers. So you can simply check this

(i/2)*2==i

Answer 2

Python

print('even' if (-1)**n==1 else 'odd')

Answer 3

Mathematica

SawtoothWave[x / 2] == 0
Exp[I Pi x] - 1 == 0
Sin[5 x / Pi] == 0

Answer 4

Brainf*** (179)

This is one of the more interesting problems involving conditional logic that I have done in BF.

+[>,]<--------------------------------------->>+++++[>+++++++
++++++>+++++++++++++++<<-]>++++>++++<<+<+<-[>-<-[>+<-[>-<-[>+<-[>-<-[>
+<-[>-<-[>+<-[>-<[-]]]]]]]]]]>[>>>.<<-<-]>[>.<-]

It takes a text input with a number. If the number is even, it outputs E, and if it is odd, it outputs O.

I'm proud enough of it that I'll show off a more human readable form:

+[>,]                                                   steps through input until it reaches eof.
<---------------------------------------                gets the numerical value of the last digit
>>+++++[>+++++++++++++>+++++++++++++++<<-]>++++>++++    store E and O
<<+<+<                                                  store a bit indicating parity, and a temporary bit
-[>-<                                                   !1
  -[>+<                                                 && !2
    -[>-<                                               && !3
      -[>+<                                             && !4
        -[>-<                                           && !5
          -[>+<                                         && !6
            -[>-<                                       && !7
              -[>+<                                     && !8
                -[>-<[-]]                               && !9
              ]
            ]
          ]
        ]
      ]
    ]
  ]
]
>[>>>.<<-<-]>[>.<-]                                     Display E or O based on the value of the parity bit.

Answer 5

C

Multiplied by itself a few times any even number will overflow to 0 given a finite size integer, and any odd number will continue to have at least the least significant bit set.

#include "stdio.h"
long long input=123;
int main(){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    if(input){
        printf("Odd");
    }
    else{
        printf("Even");
    }
    return 0;
}

Edit: As a simple function:

int isOdd(long long input){
    int a;
    for(a=6;a;a--){
        input*=input;
    }
    return !!input;
}

Answer 6

Python (Slow)

n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]

Answer 7

JavaScript

/[02468]$/.test(i)

yields true for an even number. This only works with reasonably sized integers (e.g. not scientific notation when converted to a string and not having a fractional part.)

Answer 8

Python

Since I'm not really sure what the scoring criteria are, here's a bunch of solutions I've come up with for amusement's sake. Most of them use abs(n) to support negative numbers. Most, if not all, of them should never be used for real calculation.

This one is kind of boring:

from __future__ import division
def parity(n):
    """An even number is divisible by 2 without remainder."""
    return "Even" if n/2 == int(n/2) else "Odd"

---

def parity(n):
    """In base-10, an odd number's last digit is one of 1, 3, 5, 7, 9."""
    return "Odd" if str(n)[-1] in ('1', '3', '5', '7', '9') else "Even"

---

def parity(n):
    """An even number can be expressed as the sum of an integer with itself.

    Grossly, even absurdly inefficient.

    """
    n = abs(n)
    for i in range(n):
        if i + i == n:
            return "Even"
    return "Odd"

---

def parity(n):
    """An even number can be split into two equal groups."
    g1 = []
    g2 = []
    for i in range(abs(n)):
        g1.append(None) if len(g1) == len(g2) else g2.append(None)
    return "Even" if len(g1) == len(g2) else "Odd"

---

import ent # Download from: http://wstein.org/ent/ent_py
def parity(n):
    """An even number has 2 as a factor."""
    # This also uses modulo indirectly
    return "Even" if ent.factor(n)[0][0] == 2 else "Odd"

---

And this is my favorite although it unfortunately doesn't work (as pointed out by March Ho below: just because all even numbers are the sum of two primes, doesn't mean that all odd numbers aren't).

import itertools
import ent    # Download from: http://wstein.org/ent/ent_py
def parity(n)
    """Assume Goldbach's Conjecture: all even numbers greater than 2 can
    be expressed as the sum of two primes.

    Not guaranteed to be efficient, or even succeed, for large n.

    """
    # A few quick checks
    if n in (-2, 0, 2): return "Even"
    elif n in (-1, 1): return "Odd"
    if n < 0: n = -n    # a bit faster than abs(n)
    # The primes generator uses the Sieve of Eratosthenes
    # and thus modulo, so this is a little bit cheating
    primes_to_n = ent.primes(n)
    # Still one more easy way out
    if primes_to_n[-1] == n: return "Odd"
    # Brutish!
    elif n in (p1+p2 for (p1, p2) in itertools.product(primes_to_n, primes_to_n)):
        return "Even"
    else:
        return "Odd"

Answer 9

Haskell

This is, of course, in no way the creative, thinking-outside-the-box solution you're looking for, but how many times am I going to get to post a Haskell answer shorter than GolfScript, really? It's really a shame this isn't a code golf.

odd

But more seriously:

data Parity = Even | Odd
            deriving (Show)

parity = p evens odds
  where p (x:xs) (y:ys) i | i == x = Even
                          | i == y = Odd
                          | otherwise = p xs ys i
        evens = interleave [0,2..] [-2,-4..]
        odds = interleave [1,3..] [-1,-3..]
        interleave (x:xs) ys = x : interleave ys xs

Answer 10

Using a deliberately perverse reading of the question, "How to determine if a number is odd or even", here's a C implementation (assume bool and true are defined appropriately):

bool is_odd_or_even(int n)
{
    return true;
}

Answer 11

What, no randomized algorithms yet??

C

#include<stdio.h>
#include<stdlib.h>

void prt_parity_of(int n){
  int i,j=2;
  char o[]="eovdedn"
     , f[n=abs(n)]; for(i=n;i-->0;f[i]=1);

  while(j>1){
    while((i=rand()%n)
       == (j=rand()%n)
       || (f[i]&f[j]>0)
       && (f[i]=f[j]=0)
    );for(i=j=0; ++i<n; j+=f[i])
  ;}for(;j<7;j+=2)putchar(o[j]);
}

Randomly pairs numbers in the range 0..n-1 until less than 2 are left. It's quite amazingly inefficient: O(‌n³).

---

Completely different:

Haskell

import Data.Complex

ft f = (\ω -> sum[ f(t) * exp(0:+2*pi*ω*t) | t<-[-1,-0.9..1] ] )

data Parity = Even | Odd deriving (Show)

parity n
  | all (\(re:+im) -> abs re > abs im) [ft ((:+0).(^^n)) ω | ω<-[0..20]]  = Even
  | otherwise                                                             = Odd

Uses the fact that the Fourier transform of an even function (e.g. \x->x^^4) is real, while the Fourier transform of an odd function is imaginary.

Answer 12

Windows PowerShell

function OddOrEven([long]$n) {
  if (0,2,4,6,8 -contains "$n"[-1]-48) {
    "Even"
  } else {
    "Odd"
  }
}

1. Convert to string
2. Pick last letter (digit) (essentially a mod 10).
3. Check if it is 0, 2, 4, 6 or 8.

No bitwise operators, no modulus, as requested.

Answer 13

Coq, 103

Fixpoint even n:=match n with O=>true|S n=>odd n end with odd n:=match n with O=>false|S n=>even n end.

As far as I can tell this is the first coq entry on codegolf.

Even shorter (59):

Fixpoint even n:=match n with O=>true|S n=>negb(even n)end.

Answer 14

Ruby

n.odd?

If you want to print out the result:

f[n] = ->(n){puts n.odd?? 'odd' : 'even'}

Answer 15

Unlambda

The world needs more Unlambda.

Unlambda has a killer advantage here: its default (ahem) representation for numbers are Church numerals, so all that's needed is to apply them to function binary-not to function true. Easy!

PS: Markdown and Unlambda are definitely not made for one another.

true  = i
false = `ki
not   = ``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki
even? = ``s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki

Verification for the first few integers:

```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki`ki                   => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`kii                     => `ki
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`kski           => i
```s``si`k``s``s``s`k``s``si`k`kk`k`kii`k`ki`ki`ki``s``s`ksk``s``s`kski =>`ki

Answer 16

Golfscript

~,2/),1=\;

Answer 17

Python

print (["even"] + (["odd", "even"] * abs(n)))[abs(n)]

Similar performance to the earlier version. Works for 0 now.

Incorrect Earlier version:

print ((["odd", "even"] * abs(n))[:abs(n)])[-1]

Not particularly efficient; time and memory both obviously O(n): 32 msec for 1,000,000; 2.3 msec for 100000; 3.2 usec for 100. Works with negative numbers. Throws an error for 0, because 0 is neither even nor odd.

Answer 18

Fractran

[65/42,7/13,1/21,17/7,57/85,17/19,7/17,1/3]

applied to

63*2^abs(n)

yields either 5 if n is odd or 1 if n is even.

Update: Much shorter but not so interesting:

[1/4](2^abs(n))

is 2 for odd n and 1 for even n.

Answer 19

Perl

What about

use Math::Trig;
print(cos(pi*@ARGV[0])>0?"even":"odd")

Answer 20

MMIX (4 Bytes)

This is kind of cheating. I use neither mod nor bit fiddling operations. It's rather that testing for odd / even numbers is builtin. Assuming that $3 contains the number to test and the result goes into $2:

ZSEV $2,$3,1

sets $2 to 1 if $3 is even and to 0 if not. The mnemnoric ZSEV means zero-set even and has the following semantics:

ZSEV a,b,c: if (even b) a = c; else a = 0;

For the above line, mmixal generates these four bytes of assembly:

7F 02 03 01

Answer 21

Scheme

This is the most inefficient solution I know of.

(letrec ([even? (lambda (n)
                 (if (zero? n) "even"
                     (odd? (- n 2))))]
         [odd? (lambda (n)
                 (if (= n 1) "odd"
                     (even? (- n 2))))])
  (even? (read)))

Answer 22

JavaScript, 36

function(i){while(i>0)i-=2;return!i}

Returns true if even, false if not.

Answer 23

Perl

$n x '0' =~ /^(00)*$/

Answer 24

Python

zip((False, True)*(i*i), range(i*i))[-1][0]

testing the square of i, so it works for negative numbers too

Answer 25

F#

Mutual recursion for the win.

A number n is even if it is zero or (n-1) is odd.

A number n is odd if it is unequal to zero and (n-1) is even.

(abs added in case anyone's interested in the parity of negative numbers)

let rec even n = n = 0 || odd (abs n - 1) 
    and odd n = n <> 0 && even (abs n - 1)

Answer 26

Clojure

  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))

Answer 27

What qualifies as bitwise operations? Under the hood, integer division by 2 is likely to be implemented as a bit-shift.

Assuming bitshifts aren't out:

C/C++

(unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 ? "odd" : "even"

edit Missed some parentheses, and ultimately changed to remove a shift to make it do less. You can test this with the following (in *nix):

echo 'main(){ std::cout<< (unsigned char)((unsigned char)(n > 0 ? n : -n) << 7) > 0 \
        ? "odd\n" : "even\n";}' \
  | gcc --include iostream -x c++ -o blah -
./blah

... though in Linux/tcsh, I had to escape the backslash on \n even though it was in single-quotes. I tested in little & big-endian, it works correctly in both. Also, I hand-copied this; the computer I'm posting with doesn't have a compiler, so it may have mistakes.

x86 asm

            mov eax, n          # Get the value
            cmp eax,0           # Is it zero?
            jge pos_label       # If >= 0, skip the next part
            neg eax
pos_label:

.

            imul al, 128

or

            shl  al, 7

or

            lea  eax, [eax*8]    # Multiply by 2^3 (left-shift by 3 bits)
            lea  eax, [eax*8]    # ... now it's n*2^6
            lea  eax, [eax*2]    # ... 2^7, or left-shift by 7 bits

... followed by:

            cmp al,  0          # Check whether the low byte in the low word is zero or not
            jz  even_label      # If it's zero, then it was an even number
            odd_label           # ... otherwise it wasn't

Alternatively, the shift & compare stuff could be done this way as well:

            sar al,1            # signed integer division by 2 on least-significant byte
            jc  odd_label       # jump if carry flag is set

Answer 28

On a 68000 processor you could move a word value from the address defined by the value to test:

 move.l <number to test>,a0
 move.w (a0),d0
 ; it's even if the next instruction is executed

and let the hardware trap for address error determine the odd/even nature of the value - if the exception is raised, the value was odd, if not, the value was even:

 <set up address error trap handler>
 move.l <pointer to even string>,d1
 move.l <number to test>,a0
 move.w (a0),d0
 <reset address error trap handler>
 <print string at d1>
 <end>

 address_error_trap_handler:
 move.l <pointer to odd string>,d1
 rte

Doesn't work on Intel x86 CPUs as those are more flexible about data access.

Answer 29

Python

I decided to try for the ugliest, most confusing solution I could think of:

n=input();r=range(n+1)
print [j for i in zip(map(lambda x:str(bool(x))[4],[8&7for i in r]),
map(lambda x:str(x)[1],[[].sort()for x in r])) for j in i][n]

Prints e if even, o if odd.

Answer 30

Q

Keep subtracting 2 until x<2 then convert to bool

{1b$-[;2]/[2<=;abs x]}

Answer 31

Mathematica

Edit: This is the unimaginative check that many folks, including me, use. If an integer ends in 0,2,4, 6,or 8, it is even, otherwise odd.

f[n_?IntegerQ] := Print[n, " is ", 
If[MemberQ[{0, 2, 4, 6, 8}, IntegerDigits[n][[-1]]], "even.", "odd."]]

Original solution:

The following is even more unimaginative and uselessly slow for "large" integers, but in principle, it works.

If an integer has 2 is its lowest prime factor, it is even.

f[n_?IntegerQ]:= Print[n, " is ", If[FactorInteger[n][[1, 1]] == 2, "Even", "Odd"]

Answer 32

Perl

if ((int(($number/2)) * 2) == $number) { print ("even"); }

Answer 33

Bash

This script asks Wolfram|Alpha whether a number is even or odd:

#!/bin/bash

curl -s "http://www.wolframalpha.com/input/?i=even($1)" | grep 'is even' > /dev/null

if [ $? -eq 0 ]
then
    echo Yes
else
    echo No
fi

Answer 34

Haskell, Recduction from Towers of Hanoi

When moving n pegs from A to B, then for even n, the first move is A->C.
Doesn't work for n=0.

data Peg = A|B|C deriving Eq   
third :: Peg -> Peg -> Peg
third x y
    | x/=A && y/=A = A
    | x/=B && y/=B = B
    | x/=C && y/=C = C

data Move = Move Peg Peg deriving Eq

-- Move n pegs from a to b
hanoi :: Int -> Peg -> Peg -> [ Move ]
hanoi 0 _ _ = []
hanoi n a b = (hanoi (n-1) a c) ++ [Move a b] ++ (hanoi (n-1) c b) where
    c = third a b

-- n is even if the first step in moving n discs from A to B is A->C.
iseven :: Int -> Bool
iseven n = (head $ hanoi n A B) == Move A C

Answer 35

scala:

scala> def evenOrOdd (n:Int) : Unit = n match {
     | case 0 => println ("even")              
     | case 1 => println ("odd")               
     | case _ => evenOrOdd (n-2) }             
evenOrOdd: (n: Int)Unit

scala> evenOrOdd (123456789)
odd

(less than one second)

Answer 36

Are we allowed to submit utterly terrible ways to do this? If so...

C

#include <stdio>

void oddOrEven(int number)
{
   char test[128];
   sprintf(test, "%d", number);

   int index = strlen(test) - 1;

   if((test[index]=='0')||(test[index]=='2')||(test[index]=='4')||
        (test[index]=='6')||(test[index]=='8'))
   {
      printf("Even.");
   } else {
      printf("Odd.");
   }
}

I apologize for any errors, I don't have a chance to compile or test this. Fixed one bug, per comment by Joey Adams.

This answer is similar to the one posted by idealmachine

Answer 37

Perl

sub is_odd {$#{[split/\./,$_[0]/2]}}

Answer 38

C++ (63)

Token absurd recursive solution. Even golfed!

#include <math.h>
bool o(int v){return v==0?false:!o(abs(v)-1);}

Answer 39

For C or C++, easy enough:

int Temp = 20
double Temp2 = ((double)Temp/2);
Temp2 = Temp2 - ((int)Temp/2);
if(Temp2 != 0.0)
{
    printf("It's odd!\n");
}
else
{
    printf("It's even!\n");
}

Answer 40

C#

Sorry for my previous response, I'm totally messed up today.

bool Even(int i){return i==0||!Even(i-1);}

Answer 41

function isEven(i) {
    return i == 0 || !isEven(i - (i > 0 ? 1 : -1));
}

Answer 42

return exp(sqrt(-1)*x*pi)==1?"even":"odd";

Answer 43

C++11

(for C++03, replace long long with long and -2ull with -2ul)

Yet another solution which takes advantage of the fact that integers have finite size, together with the fact that unsigned arithmetic is defined as modulo arithmetic. It also uses the fact that conversion of integer types to bool gives true iff the converted number is nonzero.

bool odd(unsigned long long n) // note: signed->unsigned conversion preserves oddity
{
  return n * (1 + -2ull / 2);
}

Answer 44

Python

Somebody already used this idea, but this implementation is more concise:

def even(n):return str(n)[-1]in'02468'

Answer 45

Squeak Smalltalk

Since printing in base 2 would be too obvious and a big waste of time because only the last digit counts

odd
    ^(self printStringBase: 2) last = $1

I decided to rather print in base 3 to at least scan all the digits

odd
    ^self ~= 0 and: [self = 1 or: [((self printStringBase: 3) occurrencesOf: $1) odd]]

Of course, if we have more CPU to waste, we can just enumerate

odd
    ^(1 to: self abs) inject: false into: [:odd :int | odd not]

Finally, if we are impatient, this might be a bit faster

odd
    (0 to: self abs by: 2) size - (1 to: self abs by: 2) size = 0

Answer 46

R

is.even<-function(n){
    options(warn=-1)
    res<-ifelse(sum(matrix(1:abs(n),nrow=2)==1)!=1, "Odd", "Even")
    options(warn=0)
    res
    }

The idea is to build a 2-rows matrix with the sequence 1 to the absolute value of n (to allow negative numbers). If the number is odd, the sequence has to be recycled to fill the 2 rows, so the matrix contains twice the number 1. Due to the method, it doesn't work with large numbers but it works with zero.

> is.even(0)
[1] "Even"
> is.even(467)
[1] "Odd"
> is.even(-46798)
[1] "Even"
> is.even(9999999999)
Error in 1:abs(n) : result would be too long a vector

Answer 47

Perl

This always returns a . when the number is odd, and either an integer or nothing when it is even.

chop($_=<>/2);print chop

If you want it to actually print the word "odd" or "even" then it needs to be expanded to the following:

chop($_=<>/2);if(chop=='.'){print"Odd"}else{print"Even"}

OR, if you want the program to exit once it gives a result, this can be written as:

chop($_=<>/2);if(chop=='.'){die"Odd"}die"Even"

Answer 48

VB.Net

return (i\2)*2=i 

Notice the use of the backslash operator \ that performs a integer division and discards any reminders. The usage of a forvard slash operator / would not work for this solution.

Answer 49

Haskell

odd = (<)0.(^)(-1)
even = (>)0.(^)(-1)

J

odd =: 0>_1&^
even =: 0<_1&^

If (-1)ⁿ<0, n is odd; if (-1)ⁿ>0, n is even.

odd =: [:|[:{:@+.0j1&^
even =: [:|[:{.@+.0j1&^

Taking the imaginary/real part of iⁿ would be a neat way to do it too, but needs better thresholding than this.

Answer 50

use queue and push pop, if element remains at last, it's odd, else is even:

var q = new Queue<int>();
for (int i=0;i<n;i++)
{
   if (q.Count > 0)
     q.Pop();
   else q.Push(0);
}

if (q.Count != 0)
  return "Odd";
return "Even";