I'm going to take @greybeard's internet points, since he apparently doesn't want them enough to type this ;-).
You need to keep in mind that \$O(x)\$ really means \$O(C \times x + ...)\$ for some value C. As long as you keep C a constant, you can do whatever you want. Thus, \$O(n)\$ can really mean \$O(2000 \times n)\$, and \$O(1)\$ can really mean \$O(10^6)\$, etc.
In this case, what @greybeard has suggested is that you count the individual set bits in all the numbers, and keep the counts in separate positions. Thus, for an array of 32-bit numbers, you would keep 32 separate counts.
Since you have to perform in \$O(n)\$, you could spend one loop through your input array determining how many bits you need to keep, so even very large numbers won't break the solution.
So let's pretend all the integers are 8-bit, just because. That doesn't mean there aren't a large number of integers, just that all the values in the array are in the range
[0, 256). What does that give you?
(If you don't know,
<< are "bitwise operators."
for each element in array:
for each bit_offset in [0..8):
if element & (1 << bit_offset):
count[bit_offset] += 1
What does that get you? It gets you a set of 8 separate counts, one for each bit in the 8-bit numbers. (Feel free to replace 8 with 64 if you like...)
Each count represents the number of times that bit appeared "set" in the input array. Now, according to your premise, all the numbers but one appear 3 times. So all the set bits will appear a multiple of 3 times. (Since set bits might be duplicated among numbers, it won't be "exactly 3 times" but instead "a multiple").
On the other hand, the one value that appears one time will have its set bits added to the counts one time. So there are two possibilities for each of the
count[i] values (note:
k[i] is some numbers that don't matter):
So you have to evaluate each
count[i] in order, and determine which form it takes:
result = 0
for bit_offset in [0..8):
if count[bit_offset] % 3 == 1:
result = set_bit(result, bit_offset)
set_bit is spelled
|= 1 << bit_offset in most C-derived languages.
In terms of efficiency, what happens?
You might process the array once by iterating over it to discover the largest number of bits required to be counted.
You create an array of N_BITS counts, initialized to zero. Since N_BITS is not related to the size of the input array, this is considered \$O(1)\$. (Actually \$O(32)\$ most likely, or maybe 64... But that's still 1 in big-O-hio!)
You iterate over the array one time, iterating over N_BITS bit values within each element. (So effectively \$O(64 \times n)\$, or less.) You compute the count values here.
You iterate over the N_BITS counts, determining the bits that will be set in the result, and setting them.
You return the result.
So your runtime is \$O(2 \times n)\$, or just n if you hard-code the N_BITS. And your memory is \$O(64)\$ or less, which is just 1.
Let's look at the example you gave in the comments:
[13, 12, 12, 3, 3, 3, 12]
First, rewrite those to binary (8 + 4 + 2 + 1):
[ 0b1101, 0b1100, 0b1100, 0b0011, 0b0011, 0b0011, 0b1100]
Now, count the set bits, just adding all the 1's in each column (no carry!):
4434 -> counts = [ 4, 4, 3, 4 ]
Next, our output will be 1 if the count is 1 (mod 3) and 0 if the count is 0 (mod 3). So [4,4,3,4] mod 3 are [1,1,0,1]:
result = 0b1101
Which is 13.