137. Single Number II

Problem Statement

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 a linear runtime complexity and use only constant 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

Constraints:

• 1 <= nums.length <= 3 * 104

• -231 <= nums[i] <= 231 - 1

• Each element in nums appears exactly three times except for one element which appears once.

Intuition

Approach 1: 
Take all store count in hashmap and move along
Uses extra space of n

Approach 2:
Lets take an example

5 5 5 4
Binary
1 0 1
1 0 1
1 0 1
1 0 0

Now in each col count ones and take mod3
So only 1 0 0 remains

TC- n*d(32 bits)

Links

https://leetcode.com/problems/single-number-ii/description/

Video Links

Approach 1:

Hash map

C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> mp;

        for(int i=0; i<nums.size(); i++)
            mp[nums[i]]++;

        for(auto &it: mp)
            if(it.second == 1)
                return it.first;

        return 0;
    }
};

Approach 2:

Bits approach

C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> count(32,0);

        for(auto &it: nums){
            int temp = it;
            for(int i=0; i<32; i++){
                if(temp&1){
                    count[i]++;
                    count[i]=count[i]%3;
                }
                temp>>=1;
            }
        }

        int ans = 0;

        for(int i=0; i<32; i++){
            if(count[i] == 0)    continue;

            int temp = 1<<i;
            ans |= temp;
        }

        return ans;
    }
};

Approach 3:

Bits extra loop optimized

C++

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int ans = 0;

    for (int i = 0; i < 32; ++i) {
      int sum = 0;
      for (const int num : nums)
        sum += num >> i & 1;
      sum %= 3;
      ans |= sum << i;
    }

    return ans;
  }
};

Approach 4:

C++

Similar Problems