Find 2 missing numbers in an array of integers with two missing values

Question

How do you do this? The values are unsorted but are of [1..n] Example array [3,1,2,5,7,8]. Answer: 4, 6

I saw this solution in another similar post, but I do not understand the last step:

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

What is the explanation for setting up that quadratic equation in the final step with z as the unknown? What's the intuition behind that being the solution to this problem?

• WhozCraig: If the post you saw (and didn't link for reference) didn't explain it well enough, is there something that suggests we can ?
• ordinary: I just linked to it. What suggests to me that someone else might be able to explain is the fact that it doesn't seem like some overly arcane algorithm, and my understanding, using the linked resource, has plateaued because of its brevity.
• Jonathan Leffler: That seems like a contorted way to process it. It would be simpler to step through the list, looking for two values of i such that a[i+1]-a[i] != 1. Since the algorithm shown also has to step through all the values in the array, there's no obvious advantage to the quadratic equation — when the data is in order. If the data is not guaranteed in order, then the solution to the quadratic equations takes linear time (O(N)) whereas a solution that sorts takes O(N.log(N)) time.
• Thomas Matthews: This is probably more math related than C++.
• sbabbi: AFAIK this problem is quite typical in job interviews. Obviously in the "original" version the input array is not sorted.

Answer 1

This method is not advisable as it suffers from integer overflow problems. So use XOR method to find the two numbers, which is highly performant. If you are interested i can explain.

As per the request from @ordinary below, i am explaining the algorithm:

EDIT

Suppose the maximum element of the array a[] is B i.e. suppose a[]={1,2,4} and here 3 and 5 are not present in a[] so max element is B=5.

• xor all the elements of the array a to X
• xor all the elements from 1 to B to x
• find the left most bit set of x by x = x &(~(x-1));
• Now if a[i] ^ x == x than xor a[i] to p else xor with q
• Now for all k from 1 to B if k ^ x == x than xor with p else xor with q
• Now print p and q

proof:

Let a = {1,2,4} and B is 5 i.e. from 1 to 5 the missing numbers are 3 and 5

Once we XOR elements of a and the numbers from 1 to 5 we left with XOR of 3 and 5 i.e. x.

Now when we find the leftmost bit set of x it is nothing but the left most different bit among 3 and 5. (3--> 011, 5 --> 101 and x = 010 where x = 3 ^ 5)

After this we are trying to divide into two groups according to the bit set of x so the two groups will be:

p = 2 , 2 , 3 (all has the 2nd last bit set)
q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)

if we XOR the elements of p among themselves we will find 3 and similarly if we xor all the elements of q among themselves than we will get 5. Hence the answer.

code in java

public void findNumbers(int[] a, int B){
 int x=0;
 for(int i=0; i<a.length;i++){
 x=x^a[i];
 }
 for(int i=1;i<=B;i++){
 x=x^i;
 }
 x = x &(~(x-1));
 int p=0, q=0;
 for(int i=0;i<a.length;i++){
 if((a[i] & x) == x){
 p=p^a[i];
 }
 else{
 q=q^a[i];
 } 
 }
 for(int i=1;i<=B;i++){
 if((i & x) == x){
 p=p^i;
 }
 else{
 q=q^i;
 }
 }
 System.out.println("p: "+p+" : "+q);
}

• ordinary: I am interested. I know if there were one number missing you could XOR all of the numbers in the first with all of the numbers in the second and the result would be the missing number, but how do you do this with two?
• ordinary: don't you mean find the right most bit? (or least significant bit)
• Trying: @ordinary just by mapping what you have and what you want to achieve. :)
• Awesome_girl: i dont understand this line of code, please explain: x = x &(~(x-1))
• Slava: "So use XOR method to find the two numbers, which is highly performant." you should mention though that your method requires 4 iterations (2 passes over array) vs only 1 pass over array on original, so depend on array size your method could be significantly slower.

Answer 2

Let x and y be the roots of a quadratic equation.

• Sum of the roots, SUM = x + y
• Product of the roots, PRODUCT = x * y

If we know the sum and the product, we can reconstruct the quadratic equation as:

z^2 - (SUM)z + (PRODUCT) = 0

In the algorithm you mentioned, we find the sum and the product, and from that, we reconstruct the quadratic equation using the above formula.

If you are interested in a detailed derivation, here is a reference. Read "Reconstruction of the quadratic equation from the sum and product of roots".

Answer 3

Starting with

x+y == SUM
xy == PRODUCT

There are two cases. If PRODUCT is zero, then one number is 0 and the other is SUM. Otherwise both are non-zero; we can multiply the first equation by x without changing the equality:

x*x + xy == x*SUM

Substitute the second equation:

x*x + PRODUCT = x*SUM

and rearrange in the usual form

x*x - x*SUM + PRODUCT = 0

So that

x = SUM/2 + sqrt(SUM*SUM - 4*PRODUCT)/2
y = SUM/2 - sqrt(SUM*SUM - 4*PRODUCT)/2

Answer 4

I have an algorithm for above problem.

Suppose

Actual Series: 1 2 3 4 5 6 a:sum=21 product= 720
Missing Number series: 1 * 3 4 * 6 b:sum=14 product= 72
a+b=21-14= 7 , ab=720/72=10

Now we need to find a-b= sqrt[(a+b)^2 -4ab].

If you calculate:

a-b= 3

Now

a+b=7
a-b=3

Add both equations:

2a=10, a=5

then b=7-5=2 so, 2 and 5 are missing.

• Vivek Singh: How does(addition truns to substraction) a+b=21-14= 7 And product turns to division ab=720/72=10?? Please explain
• Anshul Agarwal: @VivekSingh a + b + 14(sum of series with missing number) = 21 (sum including missing number a & b) that is why a + b = 21 - 14 , and similarly same goes for product as well

Answer 5

Java implementation: (Based on @Ben Voigt)

BigInteger fact=1;
int sum=0;
int prod=1;
int x,y; // The 2 missing numbers
int n=a.length;
int max=MIN_VALUE;
for (int i=0; i<a.length;i++){
 sum+=a[i]; //sums the existing numbers
 prod*=a[i]; //product the existing numbers
 if (max<a[i]) //searches for the biggest number in the array
 max=a[i];
}
while(max!=1){ //factorial for the maximum number
 fact*=max;
 max--;
}
sum=(n*(n+1))/2 - sum; //the sum of the 2 missing numbers
prod=fact/prod; //the product of the 2 missing numbers
x=sum/2 + Math.sqrt(sum*sum - 4*prod)/2;
y=sum/2 - Math.sqrt(sum*sum - 4*prod)/2;

• Ben Voigt: Note that the question gives a much more numerically stable way to find xy, based on sum of squares instead of factorial.

Answer 6

works for any number of missing elements: you can format the code a little .. but it works on duplicate and non duplicate entries also:

public static void main(String args[] ) throws Exception {
 Scanner input = new Scanner(System.in);
 System.out.println("Enter no. of students in the class");
 int N = input.nextInt();
 List<Integer> l = new ArrayList<Integer>();
 int Nn=N;
 System.out.println("Enter the roll numbers");
 for(int i=0;i<Nn;i++)
 {
 int enter=input.nextInt();
 l.add(enter); 
 }
 Collections.sort(l);
 Integer listarr[]=new Integer[l.size()];
 listarr =l.toArray(listarr);
 int check=0;
 int m1[]=new int[N];
 for(int i=0;i<N;i++)
 {
 m1[i]=i+1;
 }
 for (int i = 0; i < N; i++) {
 boolean flag=false;
 {
 for (int j = 0; j < listarr.length; j++) {
 if(m1[i]==listarr[j])
 { 
 flag=true;
 break;
 }
 else
 {
 flag=false;
 }
 }
 if(flag==false)
 {
 System.out.println("Missing number Found : " + m1[i]);
 }
 }
 }

Answer 7

Below is the generic answer in java code for any number of missing numbers in a given array
//assumes that there are no duplicates
a = [1,2,3,4,5]
b = [1,2,5]
a-b=[3,4]
public list<integer> find(int[] input){
 int[] a= new int[] {1,2,3,4,5};//create a new array without missing numbers
 List<Integer> l = new ArrayList<Integer>();//list for missing numbers
 Map<Integer,Integer> m = new HashMap<Integer>();
 //populate a hashmap with the elements in the new array
 for(int i=0;i<input.length;i++){ 
 m.put(input[i], 1);
 }
//loop through the given input array and check for missing numbers
 for(int i=0;i<a.length;i++){
 if (!m.contains(input[i]))
 l.add(input[i]);
}
 return l;
}

Answer 8

I hope this program is useful to you all, i took the limit till 10 it can be done the same way, just use n as the limit and perform the same operations.

#include <iostream>
#include<math.h>
using namespace std;
int main()
{
 int i,x[100],sum1=0,sum2=0,prod1=1,prod2=1,k,j,p=0;
 cout<<"Enter 8 elements less than 10, they should be non recurring"<<endl;
 for(i=0;i<8;i++)
 {
 cin>>x[i];
 }
 sum1=((10)*(11))/2;
 for(i=0;i<8;i++)
 {
 sum2+=x[i];
 }
 k=sum1-sum2;
 for(i=1;i<10;i++)
 {
 prod1=prod1*i;
 }
 for(i=0;i<8;i++)
 {
 prod2=prod2*x[i];
 }
 j=prod1/prod2;
 p=sqrt((k*k)-(4*j));
 cout<<"One missing no:"<<p/2<<endl;
 cout<<"Second missing no:"<<k-p/2<<endl;
}

• Ben Voigt: Note that the question gives a much more numerically stable way to find xy, based on sum of squares instead of iterated products.

Answer 9

#include <stdio.h>
#include <math.h>
/*
 the sum should be 1+...+n = n(n+1)/2
 the sum of squares should be 1^2+...+n^2 = n(n+1)(2n+1)/6.
*/
void find_missing_2_numbers(int *arr, int n);
int main()
{
 int arr[] = {3,7,1,6,8,5};
 find_missing_2_numbers(arr, 8);
 return 0;
}
void find_missing_2_numbers(int *arr, int n)
{
 int i, size, a, b, sum, sum_of_sqr, a_p_b, as_p_bs, a_i_b, a_m_b;
 size = n - 2;
 sum = 0;
 sum_of_sqr = 0;
 for (i = 0; i < size; i++)
 {
 sum += arr[i];
 sum_of_sqr += (arr[i] * arr[i]);
 }
 a_p_b = (n*(n+1))/2 - sum;
 as_p_bs = (n*(n+1)*(2 * n + 1))/6 - sum_of_sqr;
 a_i_b = ((a_p_b * a_p_b) - as_p_bs ) / 2;
 a_m_b = (int) sqrt((a_p_b * a_p_b) - 4 * a_i_b);
 a = (a_p_b + a_m_b) / 2;
 b = a_p_b - a;
 printf ("A: %d, B: %d\n", a, b);
}

Answer 10

public class MissingNumber{
static int[] array = { 1, 3, 5 };
public static void getMissingNumber() {
for (int i = 0; i < array.length; i++)
 System.out.println(array[i] + " ");
System.out.println("The Missing Number is:");
 int j = 0;
for (int i = 1; i <= 5; i++) {
 if (j < array.length && i == array[j])
 j++;
 else
 System.out.println(i + " ");
}
}
public static void main(String[] args) {
getMissingNumber();
}

}

Answer 11

Code sample(Java) for @slider answer

 /**
 * get 2 missed numbers from randomly shuffled array of unique elements from [1,n]
 *
 * @param array - shuffled array of unique elements from [1,n], but 2 random elements was missed. len = n-2
 * @return array with 2 missed elements
 */
 public static int[] getMissedNumbers(int[] array) {
 int sum = 0;
 int fullSum = 0;
 int fullProduct = 1;
 int product = 1;
 for (int i = 0; i < array.length + 2; i++) {
 int currNaturalNumber = i + 1;
 fullSum = fullSum + currNaturalNumber;
 fullProduct = fullProduct * currNaturalNumber;
 if (i < array.length) {
 sum = sum + array[i];
 product = product * array[i];
 }
 }
 int missedSum = fullSum - sum; //firstMissedNum + secondMissedNum
 int missedProduct = fullProduct / product; //firstMissedNum * secondMissedNum
 //ax*x + bx + c = 0
 //x = (-b +- sqrt(b*b - 4*a*c))/2*a
 // -b = missedSum , c = missedProduct, a = 1
 Double firstMissedNum = (missedSum + Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
 Double secondMissedNum = (missedSum - Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
 return new int[]{firstMissedNum.intValue(), secondMissedNum.intValue()};
 }

and simple arrays generator for tests

 public static Map.Entry<int[], int[]> generateArray(int maxN, int missedNumbersCount) {
 int[] initialArr = new int[maxN];
 for (int i = 0; i < maxN; i++) {
 initialArr[i] = i + 1;
 }
 shuffleArray(initialArr);
 int[] skippedNumbers = Arrays.copyOfRange(initialArr, maxN - missedNumbersCount, maxN);
 int[] arrayWithoutSkippedNumbers = Arrays.copyOf(initialArr, maxN - missedNumbersCount);
 return new AbstractMap.SimpleEntry<>(arrayWithoutSkippedNumbers, skippedNumbers);
 }
 private static void shuffleArray(int[] ar) {
 Random rnd = ThreadLocalRandom.current();
 for (int i = ar.length - 1; i > 0; i--) {
 int index = rnd.nextInt(i + 1);
 // Simple swap
 int a = ar[index];
 ar[index] = ar[i];
 ar[i] = a;
 }
 }

Answer 12

#include <iostream>
using namespace std;
int main() {
 int arr[]={3,1,2,5,7,8};
 int n=6;
 for(int i=0;i<n;i++){
 if(arr[i]>0 && arr[i]<=n){
 int temp=arr[i]-1;
 if(arr[i]!=arr[temp]){
 swap(arr[i],arr[temp]);
 i--;
 }
 }
 }
 for(int i=0;i<n;i++){
 if(arr[i]!=i+1)
 cout<<i+1<<endl;
 }
 // your code goes here
 return 0;
}

We can use the same array as a bucket. We traverse it once and keep on swapping the element to their correct index. If the value is less than 1 or more than array length, we leave it as it is. Initial Array- 3 1 2 5 7 8 swap(3,5) 5 1 2 3 7 8 swap(5,8) 8 1 2 3 7 5 After this we again traverse the array. The elements which are not in their proper position are missing hence we print the index. Time Complexity-O(n)