algoadvance

Leetcode 137. Single Number II

Problem Statement

Given an integer array nums where every element appears exactly three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Clarifying Questions

  1. Input Size: What is the size range of the input array?
    • The size of the array is not explicitly limited in the problem statement but generally, it can go up to millions.
  2. Data Range: What is the range of integers in the input array?
    • The elements in the array can be any valid integer values.
  3. Constraints on Usage:
    • You need to ensure the solution is of linear runtime complexity (O(n)) and uses only constant extra space (O(1)).

Strategy

  1. Bitwise Operation Technique:
    • We will count the number of times each bit appears in the numbers. If a bit appears three times, it contributes nothing to the unique number since every other number appears exactly three times.
    • Specifically, for each bit position i (from 0 to 31, considering the integer size), we’ll count how many times it appears across all numbers.
    • If a bit appears not divisible by 3 times (for example, 1, 4, 7 times), it should be part of the single unique number.
  2. Steps:
    • Initialize an array of 32 zeros to keep track of the count of each bit position.
    • For each number in the array, update the bit count array.
    • Finally, construct the unique number from the counts of each bit position.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bitCount[32] = {0};

        for (int num : nums) {
            for (int i = 0; i < 32; ++i) {
                if (num & (1 << i)) {
                    bitCount[i]++;
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            if (bitCount[i] % 3) {
                result |= (1 << i);
            }
        }
        
        return result;
    }
};

// Example
int main() {
    vector<int> nums = {2, 2, 3, 2};
    Solution sol;
    int result = sol.singleNumber(nums);
    // Output: 3
    return 0;
}

Time Complexity

The time complexity of this solution is O(n) where n is the number of elements in the input array. This is because we iterate through the array once and for each element, we perform a constant amount of work by iterating through 32 possible bit positions (which is a constant).

The space complexity is O(1), meaning it uses constant extra space, since our auxiliary space does not grow with the input size but remains fixed at 32 elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI