Single Number I

Bit Manipulation (9 Part Series)

1 Minimum Bit Flips to Convert Number
2 Bit Manipulation tips and tricks
… 5 more parts…
3 Power set
4 Single Number I
5 Single Number 2
6 Single number 3
7 Xor of N numbers
8 Divide two integers without using division or multiplication operators
9 Minimize XOR

Problem

We have to find the number that is present only once.
Brute force approach will be to use HashMap to keep track of count of values and then return the value having count =1;

Optimal approach using bit manipulation:

We know that 1^0 = 1, 0 ^1 = 1, 0 ^ 0 = 0 , 1 ^ 1= 0 for all other combination.
it means that exor gives 0 for same values hence if we exor all the values in the array it will give only the number whose count is 1( since rest of the value will turn 0)

TC: O(n)
SC: O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int single = nums[0];
        for(int i =1;i<nums.length;i++){
            single = single^nums[i];
        }
        return single;
    }
}

Enter fullscreen mode Exit fullscreen mode

原文链接：Single Number I