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