LeetCode - Algorithms - 260. Single Number III

Problem

260. Single Number III

Java

XOR with bitmask

In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word etc. can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation.

A bit mask is a predefined set of bits that is used to select which specific bits will be modified by subsequent operations.

the bit mask blocks the bitwise operators from touching bits we don’t want modified, and allows access to the ones we do want modified.

© https://leetcode.com/problems/single-number-iii/discuss/982092/Python3-XOR-with-bitmask

© https://www.bookstack.cn/read/solve-leetcode-problems/problems-Single%20Number%20III.md

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] singleNumber(int[] nums) {
        int xorResult = 0, firstNum = 0, secondNum = 0;
        for (int num : nums) {
            xorResult ^= num;
        }

        int bitMask = xorResult & (~xorResult + 1);

        for (int num : nums) {
            if ((bitMask & num) != 0)
                firstNum ^= num;
            else
                secondNum ^= num;
        }

        return new int[]{firstNum, secondNum};        
    }
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 1 ms, faster than 96.24% of Java online submissions for Single Number III.
  • Memory Usage: 42 MB, less than 5.92% of Java online submissions for Single Number III.

Mask (computing)