Find the element that appears once when all others appear three times.
#include <stddef.h>
#include <stdint.h>
int32_t single_number_thrice(const int32_t *a, size_t n)
{
uint32_t ones = 0, twos = 0; /* bits seen 1 time and 2 times (mod 3) */
for (size_t i = 0; i < n; i++) {
uint32_t x = (uint32_t)a[i];
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return (int32_t)ones;
}
/* {2, 2, 3, 2} -> 3, {0, 1, 0, 1, 0, 1, 99} -> 99 */
Points: each bit position counts occurrences modulo 3 using two bitmasks as a 2-bit counter; after the loop, bits of numbers that appeared three times have cancelled. O(n), O(1). A simpler version to explain first: for each of the 32 bit positions, count how many numbers have that bit set and keep it if count % 3 != 0.