Solution For Single Number
Problem Statement:
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.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Approach:
The given problem can be solved by using the XOR operator.
XOR operator, also known as the exclusive or operator, is a bit-wise operator that takes two binary numbers and performs the logical XOR operation on each pair of corresponding bits. The result of this operation is a binary number where each bit represents whether the corresponding bits of the two operands differ.
XOR can be used to determine which bits are different between two binary numbers. When you XOR two binary numbers, the resulting bits are 1 when the corresponding bits of the two operands differ; otherwise, the resulting bits are 0.
If nums=[2,2,1], as 2^2=0 and 0^1=1, the expression evaluates to 1, which is the required output.
If nums=[4,1,2,1,2], as 4⊕1⊕2⊕1⊕2=(4⊕2)⊕1⊕1⊕2=0⊕2⊕2=0⊕0=0, the expression evaluates to 4 which is the required output.
Algorithm:
- Initialize a variable called ‘output’ with 0.
- Loop through each element in the array.
- For each element, use the XOR operator to XOR it with the current value of ‘output’.
- Update the value of ‘output’ with the result of the XOR operation.
- After looping through all the elements, the final value of ‘output’ will be the single number that appears only once in the array.
Pseudo Code:
function singleNumber(nums):
output = 0
for num in nums:
output = output ^ num
return output
Complexity Analysis:
Time complexity: O(n). We are looping through each element in the array once.
Space complexity: O(1). We are using only constant extra space.
Code:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
output = 0
for num in nums:
output = output ^ num
return output
This solution has been accepted by LeetCode and passes all test cases.
Step by Step Implementation For Single Number
class Solution { public int singleNumber(int[] nums) { // create a hashmap to store the number of times each element appears in the array HashMapmap = new HashMap (); // iterate through the array and store the number of times each element appears in the hashmap for (int i = 0; i < nums.length; i++) { if (!map.containsKey(nums[i])) { map.put(nums[i], 1); } else { map.put(nums[i], map.get(nums[i]) + 1); } } // iterate through the hashmap and return the element that appears only once for (int key : map.keySet()) { if (map.get(key) == 1) { return key; } } // if no element appears only once, return -1 return -1; } }
class Solution: def singleNumber(self, nums: List[int]) -> int: # create a hashmap to store the number of occurrences of each number num_occurrences = {} # iterate through the list of numbers for num in nums: # if the number is not in the hashmap, add it and set its value to 1 if num not in num_occurrences: num_occurrences[num] = 1 # if the number is already in the hashmap, increment its value by 1 else: num_occurrences[num] += 1 # iterate through the hashmap for num, occurrences in num_occurrences.items(): # if the number of occurrences is 1, return that number if occurrences == 1: return num
var singleNumber = function(nums) { // create hashmap to store values const hashmap = {}; // iterate through array and store values in hashmap for (let i = 0; i < nums.length; i++) { if (hashmap[nums[i]]) { // if value is already in hashmap, delete it delete hashmap[nums[i]]; } else { // if value is not in hashmap, store it hashmap[nums[i]] = true; } } // return the only remaining value in hashmap return Object.keys(hashmap)[0]; };
class Solution { public: int singleNumber(vector& nums) { int result = 0; for(int i = 0; i < nums.size(); i++) { result ^= nums[i]; } return result; } };
public class Solution { public int SingleNumber(int[] nums) { // create a hashset to store all the unique numbers HashSetset = new HashSet (); // loop through the array for(int i = 0; i < nums.Length; i++) { // if the number is not in the hashset, add it if(!set.Contains(nums[i])) { set.Add(nums[i]); } // if the number is already in the hashset, remove it else { set.Remove(nums[i]); } } // return the only remaining number in the hashset, which is the single number return set.First(); } }