Single Number II
Problem Description
Given an integer array where every element appears exactly three times except for one element which appears exactly once, find that element. Must run in O(n) time and O(1) extra space.
Example 1:
Input: nums = [2,2,3,2]
Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99]
Output: 99
DE Shaw Tier 2 — LC 137.
Optimal: Bit manipulation — for each bit position, sum the bits of all numbers and take mod 3. The result bit is the singleton's bit.
Alternatively: use two variables (ones, twos) as a state machine for bits seen once/twice.
Example Test Cases
Example 1
Input: [[2,2,3,2]]
Expected: 3
Example 2
Input: [[0,1,0,1,0,1,99]]
Expected: 99
Example 3
Input: [[1]]
Expected: 1
Run your code to see the results