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.

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; } }