Problem 1
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.
Simply utilize the XOR operator’s feature: a ^ a = 0 to remove all the elements that have appeared twice:
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int n : nums) {
res ^= n;
}
return res;
}
}
Problem 2
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Since 3 is an odd number, thus, we can sum each bit of all the numbers.
If all the number appears three times, the result will be Integer multiples of 3, for example:
1001 , 1001 , 1001, 1110, 1110, 1110, sum of every bit: 6 3 3 3
for the number that appears only once, e.g: 0101
the sum will be 6 4 3 4
Indicate that the first and third bits of our target number is 1.
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (final int num : nums)
sum += ((num >> i) & 1);
sum %= 3;
ans |= sum << i;
}
return ans;
}
}
Problem 3
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Assume that the target answer is a and b
We first utilize the thinking in Problem 1, XOR all the number.
Then we get the result: a ^ b
We need to find the position, from the least significant to the most significant bit, where the binary representations of two numbers, a and b, first differ.
int lsb = xorSum == Integer.MIN_VALUE ? xorSum : xorSum & (-xorSum);
// 011 ^ 101 -> 110
// 110 补码 010
// 110 & 010 -> 010, 第二位为第一次出现不同的位置
another way：
int shift = Integer.numberOfTrailingZeros(xorAll);
then we can classify all the number in this problem into two types:
- the bit at position 2 is 0
- the bit at position 2 is 1
For any element that appears twice in the array nums, both occurrences of that element will be included in the same category;
For any element that appears only once in the array nums, such as a and b, they will be included in different categories.
Thus, we perform XOR on each categorie, then we can get a and b.
class Solution {
public int[] singleNumber(int[] nums) {
int xorSum = 0;
for (int i : nums) {
xorSum ^= i;
}
int lsb = xorSum == Integer.MIN_VALUE ? xorSum : xorSum & (-xorSum);
int type1 = 0;
int type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}
Problem 4
1486. XOR Operation in an Array
You are given an integer n and an integer start.
Define an array nums where nums[i] = start + 2 * i (0-indexed) and n == nums.length.
Return the bitwise XOR of all elements of nums.
Example 1:
Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.
Example 2:
Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8
SumXor function: calculate xor sum from 1 to n
class Solution {
public int xorOperation(int n, int start) {
int base = start >> 1;
int lastBit = n & start & 1; // only when n is odd and start is odd, can lastBit be 1.
int ret = sumXor(base - 1) ^ sumXor(base + n - 1);
return ret << 1 | lastBit; // move back and add lastBit
}
private int sumXor(int x) {
switch(x % 4) {
case 0: return x;
case 1: return 1;
case 2: return x + 1;
case 3: return 0;
}
return 0;
}
}