Sponsored
Sponsored
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
1#include <iostream>
2#include <vector>
3
4int singleNumber(std::vector<int>& nums) {
5 int result = 0;
6 for (int num : nums) {
7 result ^= num;
8 }
9 return result;
10}
11
12int main() {
13 std::vector<int> nums = {2, 2, 1};
14 std::cout << singleNumber(nums) << std::endl; // Output: 1
15 return 0;
16}singleNumber uses a range-based for loop to XOR through the vector, similarly resulting in canceling out duplicate numbers and returning the single number.
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts).
Space Complexity: O(n) - Extra space proportional to the input range.
1using System;
using System.Collections.Generic;
public class SingleNumberSolution {
public static int SingleNumber(int[] nums) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
foreach (int num in nums) {
if (countMap.ContainsKey(num))
countMap[num]++;
else
countMap[num] = 1;
}
foreach (var pair in countMap) {
if (pair.Value == 1) return pair.Key;
}
return -1;
}
public static void Main() {
int[] nums = {4, 1, 2, 1, 2};
Console.WriteLine(SingleNumber(nums)); // Output: 4
}
}This C# solution uses a Dictionary to maintain counts of each number, subsequently looking for the count equal to one to return the single number.