Today's coding problem is not very new, it's age-old classic from programming interviews. You have a sorted array containing n - 1 unique numbers starting from 0 to n - 1. There is only one number missing in this range and you need to find that out. I mean you need to write a Java method to find the missing number and print its value in the console. Some of you might have seen this question before, but if you have not been asked this question before, what is the first approach comes into your mind to solve this question? Since only one number is missing, many programmers come up with the approach of iterating over the array and comparing each element with the expected one e.g. first element should be 0, the second element should be 1 and so on. Though this will sort the problem, it will costs you O(n) time. What can you do to improve performance? The key here as we have sorted the array, do you think our earlier solution is taking full advantage of this knowledge, well it is but not fully. What it is doing is performing linear search which is costing O(n), but if you do binary search, which of course need a sorted array, we can reduce the time taken in the range of O(logN). Since numbers are in the range from 0 to n - 1 and are sorted, the first number till the missing one should be same as their indexes. I mean if 0 is not missing, then it must be in the first index i.e. at 0. If you generalize this, you will find out that if the missing number is k then all numbers less than k is located in an array with indexes same as their value. Also number k + 1 will be located at index k, and number k + 2 will be located at index k + 1. What does this mean? Well, it means that missing number is the first cell whose value is not same as its index. So our problem reduces to search in an array to find the first cell, whose value is not same as its index. You can easily find out this by using binary search algorithm in O(logN) time. Our function implements this logic to find the missing integer in a sorted array in Java. You can use this solution to find the missing number in an array of numbers 1-1000 or 1 -100.

##

Here is our complete solution of this problem. As discussed in first paragraph, solution is based upon binary search algorithm and that's why it's complexity is in logarithmic order. If you asked this question in interview, you must write production quality code, what this means is handling invalid input and boundary conditions. In our method, we are checking whether array is not null and empty before proceeding further. If you are not familiar with binary search algorithm than this diagram will help you how does it work. In binary search, instead of starting form front we start from middle element. If middle element is greater than expected number than expected number is on left hand side of middle element (lower array), otherwise it is on right hand side (higher array). So in each iteration we end up reducing our problem set by half. So in start if you have 16 element in array, next iteration you only need to search in 8 element and subsequently 4 and 2, this is how we get O(logN) complexity.

And here is our code example to find missing integer in a sorted array or series.

That's all about

The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

##
__Function to find Missing Number in Sorted Array__

And here is our code example to find missing integer in a sorted array or series.

import java.util.Arrays; /** * Java Program to find the missing number in a sorted array with integers in range 0 to n -1 * * @author Javin Paul */ public class MissingNumberFinder { public static void main(String args[]) { System.out.println("Test #1 : Missing number in sorted array "); int[] input = new int[]{1, 2, 3, 4, 6}; int missing = missingNumberFromSortedArray(input); System.out.println("Missing number from array : " + Arrays.toString(input) + " is : " + missing); } public static int missingNumberFromSortedArray(int[] numbers) { if (numbers == null || numbers.length <= 0) { throw new IllegalArgumentException("Null or Empty array not permitted"); } int left = 0; int right = numbers.length - 1; while (left <= right) { int middle = (right + left) >> 1; if (numbers[middle] != middle) { if (middle == 0 || numbers[middle - 1] == middle - 1) { return middle; } right = middle - 1; } else { left = middle + 1; } } throw new RuntimeException("No missing number"); } } Output: Test #1 : Missing number in sorted array Missing number from array : [1, 2, 3, 4, 6] is : 0

That's all about

**how do you find missing integer in an array of 0 to n - 1**. Remember you can also solve this problem with linear search and their is nothing wrong if you first come up with that solution, in fact it's very natural, but you must pay attention on sorted word. Binary search and sorted array goes hand in hand. When it comes to improving search algorithm, binary search always better than linear search.**Further Learning**The Coding Interview Bootcamp: Algorithms + Data Structures

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

if (numbers[middle] != middle) does not seem to be correct... should test for less or greater. Plus the print out finds 0, while you seem to be trying to find 5.

ReplyDeleteGreat post otherwise!

hehe

DeleteIsn't it just to find Sum of original expected vs. sum of actual resulted? Something like below program can solve very easily?

ReplyDeletepublic class MissingNumberFinder {

public static int findMissing(int[] intArr){

int last = intArr[intArr.length-1];

int first = intArr[0];

int actualSum = 0, resultedSum = 0;

for ( int i = first; i < last; i++)

actualSum +=i;

for (int i = 0; i < intArr.length-1;i++){

resultedSum += intArr[i];

}

return (actualSum-resultedSum);

}

public static void main(String args[]){

int[] arr = {1,2,3,4,5,6,7,9,10};

int result = findMissing(arr);

if ( result != 0 ){

System.out.println("Missing integer in the sorted array is: " + result);

} else

System.out.println("No missing integers");

}

}

If 0 is missing, actual sum and expected sum will be same rite??

DeleteUmesh you are still iterating the array and that too twice so your time complexity becomes 2*O(n). On the other hand the above stated method solves the problem with O(log N).

Deleteit must return 0 na??how cum 5??

ReplyDeleteHow do you find the missing number in an un-sorted array? I was asked, You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the array . One of the integers is missing in the array. Write an efficient code to find the missing integer in Java?

ReplyDeletecan I use the first solution in this case?

This also works

ReplyDeleteint sortedArray[] = { 1, 2, 4, 7, 13, 17, 18, 24 };

int naturalSeq = 0;

System.out.println("mising numbers are : ");

for (int index = 0; index < sortedArray.length; index++) {

if (naturalSeq != sortedArray[index]) {

int diff = sortedArray[index] - naturalSeq;

for (int i = naturalSeq; i < naturalSeq + diff; i++) {

System.out.println(i);

}

naturalSeq = sortedArray[index] + 1;

} else {

naturalSeq = naturalSeq + 1;

}

}

}

i was do that if not is sorted, that is the most high problem, if you try sorted that will grow complexity. also i use auxiliar structure and whit order of complexity O(2N):

ReplyDeletepublic int solution(int[] A) {

boolean[] seen = new boolean[A.length];

Arrays.fill(seen, false);

for (int value : A) {

if (0 < value && value <= A.length) {

seen[value - 1] = true;

}

}

for (int i = 0; i < seen.length; i++) {

if (seen[i] == false) {

return i + 1;

}

}

return A.length + 1;

}

also tan can be more performance in space if we use BitSet.

Gretings.

x=sumList1();

ReplyDeletey=sumList1();

missNum=|x-y|;