Single Number II

Share

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it. You must implement a solution with linear runtime complexity and use only constant extra space.

Example 1
Input: nums = [2, 2, 3, 2]
Output: 3
Explanation: 3 appears once; 2 appears three times.
Example 2
Input: nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99
Explanation: 99 appears once; 0 and 1 each appear three times.

Solution Approach

Count the number of 1-bits at each of the 32 bit positions across all numbers. If a bit position's count is not divisible by 3, the single number has a 1 in that position. Reconstruct the answer bit by bit.

  • Iterate through all 32 bit positions.
  • For each bit position, count how many numbers have that bit set.
  • If the count modulo 3 is 1, set that bit in the result.
  • Return the reconstructed result.
Java
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int bitSum = 0;
            for (int num : nums) {
                bitSum += (num >> i) & 1;
            }
            if (bitSum % 3 != 0) {
                result |= (1 << i);
            }
        }
        return result;
    }
}
Complexity Analysis:

Time complexity: O(32 * n) = O(n). 32 bit positions, each scanned once.
Space complexity: O(1). Constant extra space.