Single Number 2

Problem
HashMap approach by keeping count:

//tc : O(nlogn) : n for traversing the nums array and logn for worst case search 
//HashMap uses(Red-Black Tree) when collisions become significant, reducing the worst-case time complexity to O(log n).
//sc: O(n/3) +1
class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for(int i =0;i<nums.length;i++){
            if(map.get(nums[i]) ==1) return nums[i];
        }
        return -1;
    }
}

Bit Manipulation approach 1:
Let take example of nums[] = [2,2,3,2]; n = 4.
2 is appearing 3times and 3 is appearing 1s , hence answer is 3.

index 2	index 1	index 0
0	1	0
0	1	0
0	1	1
0	1	0

if we keep track of bit value at each index for each value that appears in nums[] then we can get the idea that if a number appears 3 times then where ever it's bit value is set to 1 that column will have (no of counts of 1)%3 = 0, if ever we get (no of counts of 1) %3 = 1 it will mean that this column(or index bit ) is set for the ans(3) we are looking for.

for the first bit (column : index 0)
(no of counts of 1) %3 = 1 -> since row three has 1 at bit index 0 (Means ans has 0th bit set)
for the second bit (column: index 1)
(no of counts of 1) %3 = 1 (Means ans has 1st bit set )
for the third bit (column: index 2)
(no of counts of 1) %3 = 0 (Means ans has 3rd bit as unset)

ans = 011 (0th and 1st bit are set) = 3(base 10)

this is what we are trying to achieve with the below code as well

//tc: O(n*32)
//sc: O(1)

class Solution {

    public int singleNumber(int[] nums) {
        int ans =0;
        //o(32)
        for(int bitIndex = 0;bitIndex<32;bitIndex++){ //since there are max 32 bits possible for the given integer value
            int count =0;
            //o(n)
//count no of 1s in ith bit for  all the nums[]
            for(int i = 0;i<nums.length;i++){
                if(((nums[i]>>bitIndex ) & 1) ==1){
                    count++;
                }
            }
            if(count%3==1){
                ans = ans | (1<<bitIndex);
            }
        }
        return ans;
    }
}

Blog

Prashant Mishra

Join Our Newsletter. No Spam, Only the good stuff.

Related