LeetCode Problem Number: 137

Single Number II

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.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Solution Code

class Solution {
public:

    void updateSum(vector &sumArr, int x){
        //extract all bits of x
        for(int i = 0 ; i < 32 ; i++){
            int ith_bit = x & (1< sumArr){
        int ans= 0 ;
        long long int power = 1;
        for(int i = 0 ; i < 32 ; i++){
            ans += power * sumArr[i];
            power *= 2;
        }
        return ans;
    }

    int singleNumber(vector& nums) {

        //first initialise the atrray of sum with all 0's.
        vector sumArr(32,0);

        //pick elements from the array and keep adding the elements in binary in the sum array.
        for(int x: nums) updateSum(sumArr, x);

        for(int i = 0 ; i < 32 ; i++){
            sumArr[i] = sumArr[i] % 3;
        }

        int ans =  getDecFromBitsArray(sumArr);
        return ans;
    }
};
                    

Solution Explanation

The problem requires finding a unique number in an array where every other number appears three times. The solution utilizes bit manipulation as follows:

• Bitwise Count: Maintain an array sumArr of size 32 to count the occurrence of each bit across all numbers.
• Bit Manipulation: For each number, update sumArr to keep track of bits set to 1.
• Modulo Operation: Take modulo 3 of each count in sumArr to find bits set by the unique number.
• Reconstruct Unique Number: Convert sumArr back to integer form to get the unique number.