Single Number I

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

The above is the detailed content of Single Number I. For more information, please follow other related articles on the PHP Chinese website!