4 ms·

I don't get it. why not just look look at the last binary bit?

• sfink 9mo ago
  Hm, good thought. You could just do printf("%d is %s\n", n, last_binary_bit(n) == 0 ? "even" : "odd"); and the rest is trivial: int last_binary_bit(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 0; ... } Come to think of it, with a little fancy math you could divide and conquer: int last_binary_bit(int n) { // Handle the easy cases. if (n == 0) return 0; if (n == 1) return 1; // Number may be large. Divide and conquer. It doesn't matter where we split it, // so use a randomized algorithm because those are fast. for (;;) { int r = random(); if (r < n) { // Smaller numbers are easier. int smaller1 = r; int smaller2 = n - 4; int bit1 = last_binary_bit(smaller1); int bit2 = last_binary_bit(smaller2); // Fancy math: even + even is even, even + odd is odd, etc. if (bit1 == 0 && bit2 == 0) return 0; if (bit1 == 0 && bit2 == 1) return 1; if (bit1 == 1 && bit2 == 0) return 1; if (bit1 == 1 && bit2 == 1) return 0; } } }