[Bit Manipulation] Single Number II

[sudosf]

Problem

Given an integer array where every element appears three times except for one element which appears exactly once, find that single element. Must run in O(n) time and O(1) space.

References

• LeetCode: https://leetcode.com/problems/single-number-ii/
• Sheet: https://www.risingbrain.org/sheet#bit-manipulation (Basic Bit Operations [Two Pointer] Container With Most Water #8)
• Parent: Pattern: Bit Manipulation #150

Difficulty

🟡 Medium

Companies

Flipkart, PhonePe, Zomato

Notes

Language: Java
Count set bits at each position modulo 3. The bit that gives remainder 1 belongs to the single element. Can also use two bitmask approach with 'ones' and 'twos'.