How do you find two missing numbers in a sequence? How do you find the missing number in a sequence? How do you find the missing number in an array?
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
Java Code Example:
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 28 29 30 31 32 33 34 35 | public class JavaExample { 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}; JavaExample f = new JavaExample(); int [] results = f.missingNumbers(arrA, 10); System.out.println("Missing numbers are :" + results[0] + " and " + results[1]); } } |
Output:
1 2 3 | Missing numbers are :6 and 4 |
Source: algorithms.tutorialhorizon.com/algorithms-find-two-missing-numbers-in-a-sequence-of-consecutive-numbers/
