Fastest way to find 2 missing numbers in an array

Question

This question exist only because of pure curiosity. Not a homework.

Find the fastest way to find two missing number in an array 1..n

So, In a related post: Quickest way to find missing number in an array of numbers I found out that you can do this pretty quickly by summing up and substracting total.

but what about 2 numbers?

So, our options are:

Sequential search
Summing up items, substracting from total for all items from 1..n, then searching all possible cases.

Anything else? Possible to have O(n) solution? I found this in ruby section of one of the websites, but any language is considered (unless there are some specific things for a language)

You could simply sort the array, which can be done in O(n log n). Afterwards you could loop over the sorted data and detected if a number i is not followed be n+1. This would add another n but would still be in O(n log n). — Martin Thurau, Dec 16 '11 at 10:30
-1. Your question is unclear. What do you mean that numbers are missing in the array 1..n (probably you meant `(1..n).to_a`)? Doesn't it include all of them? If there is some detail on the link, it still does not help. You need to state the question clearly here. — sawa, Dec 16 '11 at 14:19
"Fastest" is ill defined. Fastest algorithm and likely fastest Ruby implementation, duplicate of: http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe. Best Ruby golfer: possibly steenslag's answer. — Ciro Santilli OurBigBook.com, Jul 25 '14 at 08:54

score 29 · Answer 1 · answered Dec 16 '11 at 10:31

29

Find the sum of the numbers S=a1+...+an.
Also find the sum of squares T=a1*a1+...+an*an.
You know that the sum should be S'=1+...+n=n(n+1)/2
You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6.
Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T.
Solve by writing x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2. And now the numbers are merely the roots of the quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.

answered Dec 16 '11 at 10:31

Peteris

3,548
4
28
44

I don't get the last part of the last step. How do you know to set up that quadratic equation – ordinary Nov 17 '13 at 01:49
1

Question opened to explain last step at: http://stackoverflow.com/questions/20026243/find-2-missing-numbers-in-an-array-of-integers-with-two-missing-values?lq=1 – Ciro Santilli OurBigBook.com Jul 25 '14 at 08:57

score 24 · Accepted Answer · answered Dec 16 '11 at 10:47

24

The simple way (and pretty fast too:)

a = [1,2,3,5,7]
b = (1..7).to_a
p b-a #=> [4, 6]

answered Dec 16 '11 at 10:47

steenslag

79,051
16
138
171

4

@Michael J. Barber Array a does not have to be sorted for this to work. – steenslag Dec 16 '11 at 16:54
3

This is not _pretty fast_, since it has quadratic complexity, and there's a known and pretty simple linear solution (see answer below). – Jakub Arnold Jan 13 '15 at 11:30

score 8 · Answer 3 · answered Feb 17 '14 at 23:39

8

Assume array to be [1,4,2,3,7] . Missing numbers are 5,6

Step 1: Add all the numbers in the array. 17. We know the sum of 1..7 ( n*(n+1)/2) = 28.

Thus x+y+17=28 => x+y=11

Step 2: Multiply all the numbers in the array. 168. We know the product of 1..7 = 5040.

Thus x*y*168 = 5040 => x*y=30

(x+y)^2 = x^2 + 2xy + y^2 
=> 121 = 60 + x^2 + y^2
=> x^2 + y^2 = 61

(x-y)^2 = x^2 - 2xy + y^2 
=> (x-y)^2 = 61 - 60
=> (x-y)^2 = 1 
=> x-y = 1

We have x+y=11 and x-y=1. Solve for x,y.

This solution doesnt require additional memory space and is done in O(n).

answered Feb 17 '14 at 23:39

fragzilla

81
1
1

3

the multiplication can easily exceed the Integer.MAX_VALUE – Meow Mar 26 '14 at 05:21
This is very easy to understand. – sysuser Oct 11 '15 at 21:36

score 1 · Answer 4 · answered Dec 16 '11 at 11:25

I got the fastest time among my tests with the following approach (a little bit faster than with substitution of 2 arrays):

n = 10
input = [3, 6, 8, 2, 1, 9, 5, 7]

temp = Array.new(n+1, 0)
input.each { |item| temp[item] = 1 }
result = []
1.upto(n) { |i| result << i if temp[i] == 0 }

score 0 · Answer 5 · answered May 02 '13 at 20:08

0

What if you didn't know what the numbers in the array were? If you were just given an array and told there was a number missing, but you didn't have any knowledge of what numbers were in there you could use this:

array = array.uniq.sort!  # Just to make sure there are no dupes and it's sorted.
i = 0
while i < n.length-1
  puts n[i] + 1 if n[i] + 1 != n[i+1]
  i+=1
end

answered May 02 '13 at 20:08

mjd2

321
1
2
13

Doesn't this assume the numbers are 1 through `length-1`? Otherwise, who's to say that it isn't `-10` that's missing? – Teepeemm May 06 '16 at 19:04

score 0 · Answer 6 · edited Mar 17 '14 at 17:16

public class TwoNumberMissing {
    int fact(int x) {
        if (x != 0)
            return x * fact(x - 1);
        else
            return 1;
    }

    public static void main(String[] args) {
        TwoNumberMissing obj = new TwoNumberMissing();
        int a[] = { 1, 2, 3, 4, 5 };
        int sum = 0;
        int sum_of_ab = 0;
        for (int i = 0; i < a.length; i++) {
            sum = sum + a[i];
        }
        int b[] = {4,5,3};
        int prod = 1;
        int sum1 = 0;
        for (int i = 0; i < b.length; i++) {
            prod = prod * b[i];
            sum1 = sum1 + b[i];
        }
        int ab = obj.fact(a.length) / prod;
        System.out.println("ab=" + ab);
        sum_of_ab = sum - sum1;
        int sub_of_ab = (int) (Math.sqrt(sum_of_ab * sum_of_ab - 4 * ab));
        System.out.println("sub_of_ab=" + sub_of_ab);
        System.out.println("sum_of_ab=" + sum_of_ab);
        int num1=(sum_of_ab+sub_of_ab)/2;
         int num2=(int)ab/num1;
         System.out.println("Missing number is "+num2+" and "+num1);
    }
}

Output:

ab=2

sub_of_ab=1

sum_of_ab=3

Missing number is 1 and 2

score 0 · Answer 7 · answered Feb 06 '17 at 16:28

I propose the following solution

Bisection method on #Swift find 2 missing numbers in array

private func find(array: [Int], offset: Int, maximal: Int, missing: Int) -> [Int] {

    if array.count <= missing + 1 {
        var found = [Int]()
        var valid = offset + 1

        for value in array {
            if value != valid + found.count {
                found.append(valid)
            }
            valid += 1
        }
        return found
    }

    let maxIndex: Int = array.count
    let maxValue: Int = maximal - offset

    let midIndex: Int = maxIndex / 2
    let midValue: Int = array[midIndex - 1] - offset

    let lostInFirst: Int = midValue - midIndex
    let lostInSecond: Int = maxValue - maxIndex - lostInFirst

    var part1 = [Int]()
    var part2 = [Int]()

    if lostInFirst > 0 {
        let subarray = Array(array[0..<midIndex])
        part1 = find(array: subarray, offset: offset, maximal: midIndex + offset + lostInFirst + 1, missing: lostInFirst)
    }

    if lostInSecond > 0 {
        let subarray = Array(array[midIndex..<maxIndex])
        part2 = find(array: subarray, offset: midIndex + offset + lostInFirst, maximal: maximal, missing: lostInSecond)
    }

    return part1 + part2
}

score 0 · Answer 8 · answered Jul 08 '17 at 01:11

If the array is sorted from 0 to N then you can compare the difference with index. The recursion function for this is O(logN)
Pseudo code for it is: 
// OffsetA will keep track of the index offset of our first missing Number
// OffsetB will keep track of our second missing number
// Both Offset are set to Zero on the first recursion call. 

Missing( Array A , Array B , OffsetA,  OffsetB ){
Add Array's A and B together. Will call it array C.// At the beginning Array B would be empty.

BaseCase:  If array C.length is 2 return C

    M= C.length/2 

// for the middle value.

    If (C[M] == M + OffsetA){ // This means that both the values that are missing are to the right side of the array.
       return Missing((Arrays.copyOfRange(C,M,C.length)),ArrayB,M + Of

    fsetA,OffsetB);
    }

    If (C[M] == M + OffsetA +2){// This means both our values are to the left side of the missing array

     return Missing((Arrays.copyOfRange(C,0,M)),ArrayB,OffsetA,OffsetB);
    }

//This is the more complicated one.

`If(C[M] == M + OffsetA + 1){` This means that their are values on both the left and right side of the array. So we have to check the the middle of the first half and the middle of the second half of the array and we send the two quarter parts into our Missing Function. The checks are pretty much the same as the if statements up top but you should be able to figure out them your self. It seems like a homework or interview question. 



EDIT: There might me a small issue with the offset switching and I dont have time to change it now but you should be able to figure out the basic concept. 

}

score 0 · Answer 9 · answered Dec 16 '11 at 10:51

0

Create a set of the numbers 1 through N. Calculate the difference of this set with the set of numbers from the array. As the numbers are distinct, the result will be the missing numbers. O(N) time and space.

answered Dec 16 '11 at 10:51

Michael J. Barber

24,518
9
68
88

either the set creation or the difference calculation is slower than O(N) regardless of the implementation. – Karoly Horvath Dec 16 '11 at 10:55
1

@yi_H Use hash tables. Or, since it's a finite set, arrays of length N. Both of these are O(N). – Michael J. Barber Dec 16 '11 at 11:00

score -1 · Answer 10 · answered Dec 16 '11 at 10:20

I like the idea of summing up and comparing the result to the expected value. So my idea is to divide the array in equal parts, sum these up and see if both sides are missing a number. If one half is correct you can iterate over the other half (containing both missing numbers..... that sounds so wrong from the linguistic point of view >.<) until you managed to separate the numbers.

This approach is quite fast if abs(i-j) is big - or in words: when the missing numbers are quite far away from each other.

Fastest way to find 2 missing numbers in an array

10 Answers10

Linked