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 = 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