Back to Bit Manipulation
Easy
Single Number
Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.
Examples
Input:nums = [2,2,1]
Output:1
1 is the only number that appears once.
Input:nums = [4,1,2,1,2]
Output:4
4 is the only number that appears once.
Input:nums = [1]
Output:1
1 is the only number that appears once.
Constraints
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4Each element in the array appears twice except for one element which appears only once.
Bitwise XOR
Approach
We can use the bitwise XOR (`^`) operator. XOR has the following properties: 1. `a ^ 0 = a` 2. `a ^ a = 0` 3. XOR is commutative and associative: `a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b` If we XOR all the numbers in the array together, every number that appears twice will cancel itself out (become 0). The only number remaining will be the one that appears once.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time complexity is O(n) because we iterate through the array once. Space complexity is O(1) as we only use one variable to store the result.
Solution.java
class Solution { public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } return res; }}