Sponsored
Sponsored
This approach uses bit manipulation to solve the problem with constant space and linear runtime. The idea is to count the number of times each bit is set in the given numbers modulo 3 using two integers. This effectively filters out the bits that appear in numbers repeated thrice and leaves the bits of the unique number.
Time Complexity: O(n) - where n is the number of elements in the array.
Space Complexity: O(1) - as only a fixed amount of space is used regardless of the input size.
1public class Solution {
2 public int SingleNumber(int[] nums) {
3 int ones = 0, twos = 0;
4 foreach (int num in nums) {
5 twos |= ones & num;
6 ones ^= num;
7 int common = ones & twos;
8 ones &= ~common;
9 twos &= ~common;
10 }
11 return ones;
12 }
13
14 public static void Main() {
15 int[] nums = {2, 2, 3, 2};
16 Solution sol = new Solution();
17 Console.WriteLine(sol.SingleNumber(nums));
18 }
19}This C# solution is structurally similar to C++. Using time-efficient bit manipulation techniques, the algorithm maintains performance and clarity, employing logical operations to retain results of bits appearing less frequently than thrice.
This approach involves using a data structure to count occurrences of each number. Although this uses linear time complexity, it requires additional memory to store frequencies, which violates the constant space constraint.
Time Complexity: O(n log n) - primarily due to the sorting step.
Space Complexity: O(1) - if in-place sort is assumed.
1using System;
using System.Collections.Generic;
public class Solution {
public int SingleNumber(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int num in nums) {
if (count.ContainsKey(num)) {
count[num]++;
} else {
count[num] = 1;
}
}
foreach (var kvp in count) {
if (kvp.Value == 1) {
return kvp.Key;
}
}
return -1;
}
public static void Main() {
int[] nums = {2, 2, 3, 2};
Solution sol = new Solution();
Console.WriteLine(sol.SingleNumber(nums));
}
}This C# solution takes a dictionary approach to count and evaluate numbers. Despite its readability, it is not as efficient regarding space as required by the problem due to the extra storage needed for the frequency counts.