Sponsored
Sponsored
The idea is to use the XOR operation to find two unique numbers that appear only once in the array. This can be achieved by:
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.
1import java.util.*;
2
3public class SingleNumber {
4 public static int[] singleNumber(int[] nums) {
5 int xorAll = 0;
6 for (int num : nums) {
7 xorAll ^= num;
8 }
9
10 int diffBit = xorAll & (-xorAll);
11 int x = 0, y = 0;
12 for (int num : nums) {
13 if ((num & diffBit) == 0) {
14 x ^= num;
15 } else {
16 y ^= num;
17 }
18 }
19 return new int[]{x, y};
20 }
21
22 public static void main(String[] args) {
23 int[] nums = {1, 2, 1, 3, 2, 5};
24 int[] result = singleNumber(nums);
25 System.out.println("Single numbers are: " + result[0] + ", " + result[1]);
26 }
27}This Java solution employs a simple linear scan with bitwise operations similar to the previous approaches but uses Java's array handling capabilities to return the result in the required format efficiently.
An alternative approach that utilizes hash maps to count occurrences of each element would typically find the unique numbers. Although this solution is more straightforward, it requires additional space and does not strictly meet the problem constraints of constant extra space.
Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.
1from collections import Counter
2
3def singleNumber(nums):
4 count
This Python solution leverages collections.Counter to track occurrences and quickly find numbers appearing only once. While simple, it utilizes additional space beyond the constraints of the problem for learning purposes.