Finding the missing number in a sequential array with minimum complexity

Finding the missing number using binary search

Description :


/**
 * Find missing number in a sequence Minimum complexity (n Log n)
 *
 * input : {1,2,3,5}
 * output : 4
 */
package com.steffi.solutions;

import java.util.Arrays;

/**
 * @author Consumerfed Information Technology Section
 *
 */
public class MissingNumberArray {

private static int loopCount = 0;

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
int[] a = {1,2,3,4,6,7,8,9,10,11,12};
int len = a.length;
MissingNumberArray m = new MissingNumberArray();
int value = 0;
if(a[len-1]!=len) {
value = m.findMissingNumber(a, 0, len);
System.out.println(" The Missing number in the array :"+Arrays.toString(a)+" is "+value);
}else {
loopCount++;
System.out.println(" There is no missing number in the given array "+Arrays.toString(a));
}
System.out.println(" For "+len+" size array it tooks "+loopCount+" search to find the answer ");
System.out.println(" Complexity :"+len*Math.log(len));
System.out.println(" Time Taken : "+(System.currentTimeMillis() - startTime)+" ms");

}

private int findMissingNumber(int[] array, int startPstn, int endPstn) {
loopCount++;
int arraySize = endPstn - startPstn;
int position = startPstn + arraySize / 2;
if(arraySize==0) {
return position +1;
}else if (arraySize == 1) {
return array[position] + 1;
}
else if (array[position] != position + 1) {
return findMissingNumber(array, startPstn, position);
} else {
return findMissingNumber(array, position + 1, endPstn);

}
}
}

Output

 The Missing number in the array :[1, 2, 3, 5] is 4
 For 4 size array it tooks 2 search to find the answer
 Complexity :5.545177444479562
 Time Taken : 4 ms

 The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10] is 4
 For 9 size array it tooks 3 search to find the answer
 Complexity :19.775021196025975
 Time Taken : 4 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 10] is 9
 For 9 size array it tooks 3 search to find the answer
 Complexity :19.775021196025975
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 11] is 10
 For 10 size array it tooks 3 search to find the answer
 Complexity :23.02585092994046
 Time Taken : 2 ms

 The Missing number in the array :[1, 2, 4, 5] is 3
 For 4 size array it tooks 3 search to find the answer
 Complexity :5.545177444479562
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12] is 4
 For 11 size array it tooks 4 search to find the answer
 Complexity :26.376848000782076
 Time Taken : 3 ms

 The Missing number in the array :[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14] is 13
 For 13 size array it tooks 4 search to find the answer
 Complexity :33.34434164699998
 Time Taken : 3 ms

Buy any thing from amazon through us !!!