⭐Single Number II

Single Number II - InterviewBitInterviewBit

Thoughts

• 0:00 This is another variant of the same question that as far as I remember I was able to solve in 30 seconds. Let's see how my time this one takes.

• 1:04 I thought I got this one too. I used a map to solve this as fast as I could because I couldn't think of any other solution but I got Memory Limit Exceeded. I'll paste it here anyway.

• 3:15 Now I can think in peace since there is no pressure to complete it in an unrealistically small amount of time.

• 7:15 The problem statement clearly says it wants a $O(n)$​ solution but I really want to give sorting an attempt. Just for practice. I'll go ahead and do that.

• 14:50 Why am I finding the sorting approach hard to implement? Am I being careless?

• Ok, so it turns out my sorting solution has been accepted.

• I will try thinking in terms of bit manipulation. Since this question belongs to that section.

• 18:30 I'm not able to think of a solution. I'll take a hint.

• 22:00 Hint couldn't help either so I saw the solution approach. Each number that appears thrice will contribute 3 1s and 0s in all the 32 bits for itself. The number that appears once will only make this contribution once. So the bits that are present $3x+1$​ are the bits set by the single number.

• Let me try using an array for this. The solution talks about using a bit-mask but that sounds too complicated.

• 31:00 I coded something but it's not working at all. I'll take it to Online GDB. last 15 min. Then I'll see the solution.

• 42:00 Ok, I'm just not able to solve this. I'll see the solution now.

• 48:00 None of the solutions they have posted in the editorial makes sense. I'll find a YouTube Video.

• 1:01:00 Tech Dose teaches very well. Wonder why he has so few likes.

• 1:09:50 I've got the intuitive solution but I have no will to go for the unintuitive optimal solution. I'll just let it be for now.

Using Map

int Solution::singleNumber(const vector<int> &A) {
    map<int, int> freq;
    for(int x: A)
        freq[x]++;
        
    for(auto p: freq)
        if(p.second == 1)   
            return p.first;
        
    return -1;
}

Time Complexity: $O(n)$​

Space Complexity: $O(n)$​

Using Sorting

int Solution::singleNumber(const vector<int> &A) {
    vector<int> B(A.begin(), A.end());
    sort(B.begin(), B.end());
    int i = 0;
    while(i + 1 < A.size()) {
        if(B[i] != B[i + 1])
            return B[i];
        i = i + 3;
    }
    
    if(A.size() == 1)
        return B.front();
    else
        return B.back();
}

Time Complexity: $O(n\log n)$​

Space Complexity: $O(n)$ for duplicating array for sorting

Counting Set Bits

int Solution::singleNumber(const vector<int> &A) {
    int res = 1;
    for(int shift = 0; shift < 32; shift++) {
        int count = 0;
        for(const int &x: A) 
            count += x & (1<<shift);
        
        if(count % 3)
            res = res | (1 << shift);
    }    
}