Given a
non-empty array of integers, every element appears
twice except for one. Find that single one.
>> Solution 1: Using list - O(n^2) time, O(n) space
/**
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
*
* Performance: O(n^2) time, O(n) space
*
*/
public int singleNumber(int[] nums) {
// O(n) space
List<Integer> allElements = new ArrayList<>();
// O(n^2) time
for(int n : nums){
Integer nWrapped = Integer.valueOf(n);
if(allElements.contains(nWrapped)){
allElements.remove(nWrapped);
} else {
allElements.add(nWrapped);
}
}
return allElements.get(0);
}
Solution 2: Using hash map, O(n) time, O(n) space
/**
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
*
* Performance: O(n) time, O(n) space
*
*/
public int singleNumber(int[] nums) {
Map<Integer, Integer> elementCounts = new HashMap<>();
// O(n) time, O(n) space
for(int n : nums){
Integer wrappedVal = Integer.valueOf(n);
int currentCount = elementCounts.getOrDefault(wrappedVal,0)+1;
elementCounts.put( wrappedVal , currentCount );
}
// O(n) time, O(1) space
for(int n : nums) {
Integer wrappedVal = Integer.valueOf(n);
if(elementCounts.get(wrappedVal) == 1) {
return n;
}
}
throw new UnsupportedOperationException("Not a correct input set");
}
Solution 3a: Using math, O(n) time, O(n) space
/**
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
*
* Performance: O(n) time, O(n) space
*
* sumOfSet = a+b+c
* sumOfNums = c + 2*(a+b+c)
* sumOfNums = c + 2*sumOfSet - c
* c = 2*sumOfSet - c
*/
public int singleNumber(int[] nums) {
// O(n) time, O(1) space
int sumOfNums = IntStream
.of(nums)
.sum();
// O(n) time, O(n) space
int sumOfSet = IntStream.of(nums)
.boxed()
.collect(Collectors.toSet())
.stream()
.mapToInt(Integer::intValue)
.sum();
return 2*sumOfSet - sumOfNums;
}
Solution 3b: Using math, O(n) time, O(n) space - but better runtime
/**
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
*
* Performance: O(n) time, O(n) space
*
* sumOfSet = a+b+c
* sumOfNums = c + 2*(a+b+c)
* sumOfNums = c + 2*sumOfSet - c
* c = 2*sumOfSet - c
*/
public int singleNumber(int[] nums) {
int sumOfNums = 0;
int sumOfSet = 0;
Set<Integer> elements = new HashSet<>(); // O(1) space
// O(n) time
for(int n : nums) {
Integer intWrapped = Integer.valueOf(n);
if(!elements.contains(intWrapped)) {
elements.add(intWrapped);
sumOfSet += n;
}
sumOfNums += n;
}
return 2*sumOfSet - sumOfNums;
}
Solution 4 : Bit operations, O(n) time, O(1) space
/**
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
*
* Performance: O(n) time, O(1) space
*
* a XOR 0 = n
* a XOR a = 0
* a XOR b XOR a = a
*/
public int singleNumber(int[] nums) {
// O(1) space
int result = 0;
// O(n) time
for(int n : nums) {
result = result ^ n;
}
return result;
}
