Return to Blog entry

C solution wiennat 19th November, 2008 04:33 (UTC)

Given n is the integer we want to know if it is even or odd. We can divide the problem into 2 cases.

  • case: (n < 2)

n == 0, n is even n == 1, n is odd

  • case : (n > 2)

Step 1: Given i=1

Step 2: If i+i is less than n then i = i+i If i+i is more than or equal to n, subtract i from n.

Step 3: Repeat step 2 until n < 2. We can achieve the answer b case (n<2).

Here is my C solution.

First, find the multiple of 2 which more than given input “in”. This is O(log n).

Then, repeatly subtract “in” with the highest number of multiple of 2 that less than “in” until “in < 2”. This is O(log n)

Finally, the function will return 1 if “in” is odd. Otherwise, return 0

int odd(int in){

    int b, c;
    int maxi = 8;
    int max  = 1;
    int i    = 1;
    int *a   = NULL;
    a = (int *)malloc(sizeof(int) * maxi);

    a[0] = 2;

    while (in < max+max){
        if (i == maxi){
            maxi *= 2;
            a = (int *)realloc(a, sizeof(int) * maxi * 2);
        }
        a[i] = a[i-1]*2;
        i++;
    }
    b = in-a[i];
    do {
        for(c=i-1; a[c]>b && c >= 0;c—);
        b -= a[c];
    } while (b >= 2);
    free(a);
    return b;
}

Edited code layout, hope I didn't break anything, kirit

kirit.com