Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by dmckee Mar 16 '13 at 19:22

Questions on Programming Puzzles & Code Golf Stack Exchange are expected to relate to programming puzzle or code golf within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
Should we create a function or a program? How should IO happen if we have to do a program? Please, elaborate further. –  Juan Apr 28 '11 at 3:10
2  
What objective criterion will determine the accepted answer? Code size? Something else? –  PleaseStand Apr 28 '11 at 3:47
    
Is it definitely a number? Should it give false positives for a string? –  Liam William Apr 30 '11 at 1:22
    
This has been around for quite a long time, but there doesn't seem to be a winning condition of any kind, which to my mind means there is no game here. –  dmckee Mar 16 '13 at 19:22

50 Answers 50

up vote 31 down vote accepted

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

(i/2)*2==i
share|improve this answer
5  
Not necessarily most, I'd say. Many, maybe. –  Joey Apr 28 '11 at 10:25
1  
to ensure it runs properly, you need to make sure you cast everything into an int/long type –  warren Apr 28 '11 at 13:23
    
@warren Depends on the programming language/compiler optimizations/etc. Additionally, you can use floor(). That works perfectly in C and C++. –  muntoo May 1 '11 at 21:03
1  
Is 0 a even number? –  user unknown Aug 13 '11 at 23:58
3  
@userunknown: Yes, zero is even. –  Keith Thompson Nov 5 '11 at 18:40

Python

print('even' if (-1)**n==1 else 'odd')
share|improve this answer
7  
The simple beauty / beautiful simplicity of mathematics...very nice! –  Josh Caswell Apr 28 '11 at 16:15
    
I like this one a lot. –  Rob Oct 11 '11 at 19:21
    
Slow but creative. –  muntoo Nov 1 '11 at 23:31

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.
share|improve this answer

Mathematica

SawtoothWave[x / 2] == 0
Exp[i pi x] - 1 == 0
Sin[5 x / pi] == 0
share|improve this answer
3  
+1 for regexp.. –  st0le Apr 28 '11 at 4:36
2  
Can you split these two solutions into different answers? –  FUZxxl Apr 28 '11 at 8:00
    
Aren't those four solutions? –  Joey Apr 28 '11 at 8:47

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;
}
share|improve this answer
    
Be sure to use unsigned integers. Overflow of signed integers is undefined behavior in C, so optimization could do something weird if it wanted. –  Joey Adams Sep 10 '11 at 8:57

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

share|improve this answer
2  
To meet the "function" requirement you could change it to simply /[02468]$/.test. –  minitech Apr 28 '11 at 18:12
    
It wasn't exactly clear in the question but it could be possible that the input isn't a number at all, /[02468]$/.test('I am a fake even number 0'). In that case you could do /^[0-9].[02468]$/.test(i) –  Liam William Apr 30 '11 at 1:23
    
/-?^\d*[02468]$/ would be a little stricter than your regex. You would need more work for this to work properly for numbers that are toString'ed using scientific notation. –  Thomas Eding Aug 26 '11 at 19:32

Python (Slow)

n=1234
while n > 1: n -= 2 #slow way of modulus.
print "eovdedn"[n::2]
share|improve this answer
1  
Works for positive...i suppose i could add a abs() call in the beginning. –  st0le Apr 28 '11 at 4:34
3  
+1 for style in printing the result –  Josh Caswell Apr 28 '11 at 6:42
    
@Josh: That trick appeared here a few times already by now :) –  Joey Apr 28 '11 at 10:25
    
Credits to gnibblr :) –  st0le Apr 28 '11 at 11:21
    
@Joey: I didn't figure it was new, but style doesn't have to be original. :) –  Josh Caswell Apr 28 '11 at 15:36

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
share|improve this answer
    
looks longer than the GolfScript answer to me –  warren Apr 28 '11 at 13:26
2  
I was referring to the first block (odd) which is a builtin function that returns True if the number is odd. That's a complete answer on its own and shorter than the current GolfScript answer (which at the time of writing this is 10 chars, but I expect that to go down). The question is also a bit underspecified, which is why I assert that odd is sufficient. That may change as well. –  jloy Apr 28 '11 at 16:02
1  
missed the first reply in your answer :) –  warren Apr 28 '11 at 16:23
1  
At the very least the parity algorithm works on all Num instances that are integers. That's hot! Though I probably would have done evens = [0,2..] >>= \n -> [-n, n]. Similar for odds. –  Thomas Eding Aug 26 '11 at 19:38

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:

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"
share|improve this answer
    
Cute solutions :-) –  Joey May 4 '11 at 14:42

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;
}
share|improve this answer
    
The question mentions number, not integer. Number like 0.5 returns true when it shouldn't. –  xfix Mar 18 at 19:19

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.

share|improve this answer

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(‌n3).


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.

share|improve this answer

Ruby

n.odd?

If you want to print out the result:

f[n] = ->(n){puts n.odd?? 'odd' : 'even'}
share|improve this answer
    
I'm fairly use ruby uses mod in the .odd? definition. –  MrZander Mar 15 '13 at 23:49

Golfscript

~,2/),1=\;
share|improve this answer

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.

share|improve this answer
2  
Zero is definitely even. See also: en.wikipedia.org/wiki/Parity_of_zero –  jloy Apr 28 '11 at 7:14
    
@jloy: Aw, crap. I thought that was "a feature, not a bug". More revisions... –  Josh Caswell Apr 28 '11 at 7:16

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
share|improve this answer

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
share|improve this answer

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)))
share|improve this answer

Perl

What about

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

JavaScript, 36

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

Returns true if even, false if not.

share|improve this answer

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.

share|improve this answer

Python

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

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

share|improve this answer

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)
share|improve this answer

Clojure

  (defmacro even?[n]
  `(= 1 ~(concat (list *) (repeat n -1))))
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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"]
share|improve this answer

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

share|improve this answer
    
You'll need strlen(test) - 1 for this to work. test[index] currently refers to the null terminator of the string. –  Joey Adams Apr 28 '11 at 15:26
    
@Joey Adams Thanks, I knew there'd be at least one bug. –  thedaian Apr 28 '11 at 15:39
    
Considering efficiency isn't a metric here, this solution is as good as any really. –  Neil Sep 14 '11 at 13:37

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)

share|improve this answer

Perl

$n x '0' =~ /^(00)*$/
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.