The Two Numbers That Disappeared

Posted on Edited on In Waline:

Given an array containing all integers from 1 to N, but two numbers are missing. Can you find them in O (N) time using only O (1) space?

Link to the topic: https://leetcode.cn/problems/missing-two-lcci/

This problem is not strictly an algorithm problem. I feel that in its solution, one kind of knowledge is like binary knowledge in computer composition, and the other is mathematical knowledge

Summation

This method is a purely mathematical method.

  • We know that the sum of 1~ N is $\ frac {N (N + 1) } {2} $, then we can find the sum of the provided N-2 numbers by ergodic method, and by subtraction, we can get The sum of the missing two numbers, assuming’sumTwo ', the missing two numbers are a and b respectively
  • The two missing numbers are not the same, so one is larger and the other is smaller, that is, one is less than the average of the two, and one is greater than the average of the two. Assuming the average is’limit ', then $limit =\ frac {sumTwo} {2} $
  • Then divide 1~ N into two parts according to whether it is less than’limit ', then a is between 1~ limit, we only need to calculate the sum of 1~ limit, that is, $\ frac {limit (limit + 1) } {2} The difference between $and the sum of the numbers 1~ limit in the provided array is actually a. Find b the same
1
2
3
4
5
6
7
8
9
10
11
12
13
var missingTwo = function(nums) {
    const N = nums.length + 2;
    const sumTwo = (N * (N + 1)) / 2 - nums.reduce((pre, cur) => (pre + cur), 0);
    const limit = Math.floor(sumTwo / 2);
    let sumBefore = 0;
    for(const num of nums) {
        if (num <= limit) {
            sumBefore += num;
        }
    }
    const one = (limit * (limit + 1)) / 2 - sumBefore;
    return [one, sumTwo - one];
};

Using bit operation

This idea is somewhat similar to the above summation idea. It is to first obtain the combined result of the missing two numbers, and then divide the provided numbers into two parts according to the combined result. The missing two numbers are in two parts respectively. in.

The length of the array is n - 2 because two of the integers from 1 to n disappear and every other integer appears in the array once. Adding each integer from 1 to n after the n - 2 numbers in the array once results in 2n − 2 numbers, with two missing numbers in the array appearing once each and each other appearing twice each.

Suppose the two numbers missing from the array nums are $x_1 $, $x_2 $. If you XOR all the above 2n − 2 numbers to get the result x, then there must be:

x=x1⨁x2x = x_1 \bigoplus x_2

Where $\ bigoplus $represents the exclusive OR operation. This is because the elements that appear twice in nums will be offset by the property of the exclusive OR operation $a\ bigoplus b\ bigoplus b = a $, so the final result is only the exclusive OR sum of $x_1 $, $x_2 $.

Obviously $x\ ne 0 $, because if x = 0, then $x_1 = x_2 $, $x_1 $, $x_2 $is not a number that only appears once in the above 2n - 2 numbers. Therefore, we can use the bit operation $x & -x $to take the lowest bit 1 in the binary representation of x and set it to the lth bit, then the lth bit of the binary representation of $x_1 $, $x_2 $is 0, and the lth bit of the binary representation of another number is 1. In this case, the lth bit of the binary representation of $x_1\ bigoplus x_2 $can be 1.

In this way, we can divide all integers from 1 to n into two categories, one containing all binary representations of numbers with the lth bit of 0, and the other containing all binary representations of numbers with the lth bit of 1. It can be found:

For any number that appears once in the array nums, these numbers appear twice in the above 2n − 2 numbers, and both occurrences will be included in the same class;

For any number that disappears from the array nums, i.e. $x_1 $, $x_2 $, these numbers appear once in the above 2n - 2 numbers and will be included in a different class.

Therefore, if we XOR all the elements of each class, then one class will get $x_1 $and the other class will get $x_2 $. This way we find these two elements that only appear once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var missingTwo = function(nums) {
    let xorsum = 0;
    let n = nums.length + 2;
    for (const num of nums) {
        xorsum ^= num;
    }
    for (let i = 1; i <= n; i++) {
        xorsum ^= i;
    }
    let type1 = 0, type2 = 0;
    const lsb = xorsum & (-xorsum);
    for (const num of nums) {
        if (num & lsb) {
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    for (let i = 1; i <= n; i++) {
        if (i & lsb) {
            type1 ^= i;
        } else {
            type2 ^= i;
        }
    }
    return [type1, type2];
};