mediumCodingConceptEntryMidSenior
Every number in the array appears three times except one. Find the single number in O(1) extra space, and make sure it works for negatives.
Count, for each of the 32 bit positions, how many numbers have that bit set, and keep the count modulo 3. Tripled values contribute multiples of 3, so the bits with a remainder belong to the single number. Setting bit 31 makes a Java int negative, so negative answers come out right in O(32n) time and constant space.
5 min readUpdated 2026-10-09Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Use bit counting by position. For each of the 32 bit positions, count how many numbers have that bit set and take the count modulo 3. Every value that appears three times adds 0 or 3 to each position, so whatever remains is the single number's bit. In Java, setting bit 31 of an int makes it negative, which is exactly how two's complement represents a negative answer, so no sign fix-up is needed.
Was this answer helpful?
Likely follow-ups
- The unique value appears twice instead of once. Which of your two solutions still works, and why does the other return 0?
- Every value appears five times except one. What changes in the code and in the cost?
- Why is O(32n) honestly constant space but a misleading description of time for small arrays?
- How would you solve this for 64-bit values, and what goes wrong if the shift literal is still an int?
Related questions
- Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.mediumAlso on bit-manipulation and twos-complement4 min
- Every value in an array appears twice except one. Find it, and tell me when bit tricks are worth reaching foreasyAlso on bit-manipulation5 min
- Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?hardAlso on bit-manipulation4 min
- You need to find a substring in linear time and the interviewer will not accept a library call. What do you compute, and what goes wrong on a collision?mediumAlso on modular-arithmetic5 min