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;
}
}
Top comments (0)