Home  >  Article  >  Java  >  Single Number I

Single Number I

DDD
DDDOriginal
2024-09-19 06:17:33518browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn