136. Single Number

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.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 10<sup>4</sup>

• -3 * 10<sup>4</sup> <= nums[i] <= 3 * 10<sup>4</sup>

• Each element in the array appears twice except for one element which appears only once.

Use exclusive OR(XOR, ^). XOR means:

if a != b, a ^ b == 1.

if a == b, a ^ b == 0.

0^0=0，1^0=1，0^1=1，1^1=0

So, when we perform bitwise operations on these numbers, it is easy to get that a^b^a = b.

class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        for(int i=1;i<nums.length;i++){
            ans = ans^nums[i];
        }
        return ans;
    }
}

Accepted

1 ms

44.7 MB

java

137. Single Number II

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.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

• 1 <= nums.length <= 3 * 10<sup>4</sup>

• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

• Each element in nums appears exactly three times except for one element which appears once.

Now, it becomes much difficult ahh. We can't use that trick again to solve this problem because a^b^a^a = b^a.

But the core idea is bitwise operation, too.

Let's think about this case now.

[2, 2, 3, 2, 3, 3, 6]

Elements in this array are repeated 3 times except '6'

We can transfer these numbers into binary numbers

2 = 0010
3 = 0011
6 = 0110

0010
0010
0010
---------
0030 (Each digit is a multiple of 3)

0011
0011
0011
---------
0033 (Each digit is a multiple of 3)

0110 (Each digit is not a multiple of 3)
---------
0173

0 % 3 = 0
1 % 3 = 1
7 % 3 = 1
3 % 3 = 0

0110 == 6

Let's write the code!

class Solution {
    public int singleNumber(int[] nums) {
        int[] re = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                re[i] += (num >> i) & 1;
            }
        }
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += (re[i] % 3) << i;
        }
        return result;
    }
}

'&' means the bitwise AND

1 & 1=1, 1 & 0=0, 0 & 0=0, 0 & 1=0

But, when we wrote the code in Python 3, an exception occurred:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        re = [0]*32
        for num in nums:
            for i in range(32):
                re[i] += (num >> i) & 1
        result = 0
        for i in range(32):
            result += (re[i] % 3) * pow(2, i)
        return result

input: [-2,-2,1,1,4,1,4,4,-4,-2]
output: 4294967292

In Python, integers are infinite-bit, which means you can represent very large or very small integer values without a 32-bit limit.

But in many other programming languages(such as Java) and computer hardware, integers are usually represented using a fixed number of bits, such as 32 or 64 bits.

In this algorithm, when re[i] % 3 is calculated for each bit, the complement representation of -4 is finally formed. But when you manipulate this result directly in Python, Python thinks it's an unsigned large number, so you get 4294967292, which is equal to 2^32 - 4.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        re = [0]*32
        for num in nums:
            for i in range(32):
                re[i] += (num >> i) & 1
        result = 0
        for i in range(32):
            result += (re[i] % 3) * pow(2, i)

        if (result >> 31) == 1:  # result (decimal) < 0
            result -= pow(2, 32)
        return result

Accepted

2 ms

43.9 MB

java

260. Single Number III

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.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Constraints:

• 2 <= nums.length <= 3 * 10<sup>4</sup>

• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

• Each integer in nums will appear twice, only two integers will appear once.

Now, it's the final question in this blog.

Idea:

① Perform the XOR (^) operation on all elements of the array to obtain the XOR result diff of the two numbers.

②. diff &= -diff, get the first different position a in the binary form of the two numbers that only appears once.

③ Initialize the result array [0, 0], traverse the elements in the array, if a = 1, perform XOR with the first element in the result array; if a = 0, perform XOR with the second element.

④. Return the result array.

    public int[] singleNumber(int[] nums) {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = 0;
        for(int num: nums)
            diff ^= num;
        // Get its last set bit
        diff &= -diff;

        // Pass 2 :
        int[] rets = {0, 0};
        for(int num: nums) {
            if((num & diff) == 0)
                rets[0] ^= num;
            else 
                rets[1] ^= num;
        }
        return rets;
    }

def singleNumber(nums):
    # Pass 1:
    # Get the XOR of the two numbers we need to find
    diff = 0
    for num in nums:
        diff ^= num
    # Get its last set bit
    diff &= -diff

    # Pass 2:
    rets = [0, 0]
    for num in nums:
        if (num & diff) == 0:
            rets[0] ^= num
        else:
            rets[1] ^= num

    return rets