Description
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:
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1Solution in Python
To solve the problem of finding the single element in an array where every element appears twice except for one, we can use a bit manipulation technique called XOR. The key properties of XOR that we will leverage are:
- Commutative and Associative Properties: The order in which we apply XOR does not matter.
- Identity Property: a⊕0=a
- Self-inverse Property: a⊕a=0
Using these properties, we can XOR all the elements in the array together. Pairs of the same number will cancel each other out (since a⊕a=0), leaving the single number that appears only once.
Python
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# Initialize result with 0
result = 0
# Iterate through each number in the array
for num in nums:
# XOR the current number with the result
result ^= num
# The result now holds the single number that appears only once
return resultExplanation
- Initialization: Start with a variable
resultset to 0. - Iterate through the Array: For each number in the array, perform an XOR operation between
resultand the current number. - XOR Operation: XOR operation between the same numbers will cancel out to 0, and XORing with 0 will retain the number. Therefore, pairs of numbers will cancel each other out, leaving the single number.
- Return the Result: After processing all numbers,
resultwill contain the single number that appears only once.
This solution meets the requirements of linear runtime complexity O(n) and constant extra space O(1).
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
// Initialize result with 0
let result = 0;
// Iterate through each number in the array
for (let i = 0; i < nums.length; i++) {
// XOR the current number with the result
result ^= nums[i];
}
// The result now holds the single number that appears only once
return result;
};Solution in Java
Java
class Solution {
public int singleNumber(int[] nums) {
// Initialize result with 0
int result = 0;
// Iterate through each number in the array
for (int num : nums) {
// XOR the current number with the result
result ^= num;
}
// The result now holds the single number that appears only once
return result;
}
}Solution in C#
C#
public class Solution {
public int SingleNumber(int[] nums) {
// Initialize result with 0
int result = 0;
// Iterate through each number in the array
foreach (int num in nums) {
// XOR the current number with the result
result ^= num;
}
// The result now holds the single number that appears only once
return result;
}
}