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= SumN–Sum; | |
| 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*s–4*product); // (a-b)^2 = (a+b)^2-4ab | |
| a = (s+diffSqr)/2; | |
| b= s–a; | |
| 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
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)