Find two Missing Numbers in a Sequence of Consecutive Numbers

Objective : Write an algorithm to find two Missing Numbers in a Sequence of Consecutive Numbers

Input:  Array, arrA[] with two missing numbers and Range

Output : Two missing numbers

Approach:

    • Approach is very simple, Add all the given numbers say S
    • Calculate sum of N numbers by formula n(n+1)/2 , say N
    • Find sum of two missing numbers a+b = N-S

  • Now take the product of all given numbers say P
  • Now take the product of N numbers , say Np;
  • Find the product of two missing numbers ab = Np-P
  • Now we have a+b and ab , we can easily calculate a and b

Example :

Given array : {10,2,3,5,7,8,9,1}; Range : 10

N (Sum of 1 to 10 ) = 55

S (Sum of given elements ) = 45

a+b = 10------------------------------------(1)

Np(Product of 1 to 10) = 3628800

P(Product of given elements) = 151200

So a*b = 24---------------------------------(2)

Now we have two equations and two variables, if we solve we will get values 6 and 4.

Complete Code:

//find the two missing numbers from the sequence of consecutive number
//Approach is very simple, Add all the given numbers say S
//Calculate sum of N numbers by formula n(n+1)/2 , say N
//Find sum of two missing numbers a+b = N-S
//Now take the product of all given numbers say P
//now take the product of N numbers , say Np;
//find the product of two missing numbers ab = Np-P
//now we have a+b and ab , we can easily calculate a and b
public class FindTwoMissingNumbers {
int Sum;
int SumN;
int P=1;
int Np=1;
int a,b;
public int [] missingNumbers(int [] arrA, int range){
SumN = range*(range+1)/2;
for(int i=0;i<arrA.length;i++){
Sum +=arrA[i];
}
int s= SumNSum;
for(int i=0;i<arrA.length;i++){
P *=arrA[i];
}
for(int i=1;i<=range;i++){
Np *=i;
}
int product = Np/P;
// System.out.println(product);
int diffSqr = (int)Math.sqrt(s*s4*product); // (a-b)^2 = (a+b)^2-4ab
a = (s+diffSqr)/2;
b= sa;
int [] result = {a,b};
return result;
}
public static void main(String args[]){
int [] arrA = {10,2,3,5,7,8,9,1};
FindTwoMissingNumbers f = new FindTwoMissingNumbers();
int [] results = f.missingNumbers(arrA, 10);
System.out.println("Missing numbers are :" + results[0] + " and " + results[1]);
}
}

Output:

Missing numbers are :6 and 4

 

1 thought on “Find two Missing Numbers in a Sequence of Consecutive Numbers”

  1. The example is very good, just a small bug at line 30 in the snippet, it should be (s*2) not (s*s) in the equation
    diffSqr = (int)Math.sqrt((s*s)-4*product)

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.