I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Find The Missing Number

02.28.2013
| 7356 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Find the Missing Number in the Array

Given a sorted array of numbers from 0 to n, with only one number missing in the sequence, write a method that will find that number.

Catch up on all our previous puzzlers here.

Comments

Ajinkya Vaze replied on Thu, 2013/02/28 - 8:28am

//Finds missing number by iterating through the array
	private int findMissingNumber(int[] numbers) {
		int missingNumber = 0;
		for (int i = 0; i < (numbers.length - 1); i++) {
			if ((numbers[i + 1] - numbers[i]) > 1) {
				missingNumber = numbers[i] + 1;
				break;
			}
		}
		return missingNumber;
	}

//Using formula sum of n numbers in sequence is (n * (n + 1)) / 2
	private int findMissingNumber1(int[] numbers) {
		int lastNumber = numbers[numbers.length - 1];
		int expectedSum = (lastNumber * (lastNumber + 1)) / 2;
		int actualSum = 0;
		for (int i = 0; i < numbers.length; i++) {
			actualSum += numbers[i];
		}
		return expectedSum - actualSum;
	}

Vijay Nathani replied on Thu, 2013/02/28 - 9:02am in response to: Ajinkya Vaze

This is a trick question.

Basically, the fastest way to do the same will be to use binary search. Instead of the algorithm being O(n), it will be O(log n) with base 2 for logarithm.

Groovy Solution

def missingNumber(def sortedNumbers) {
	def (begin, end) = [0, sortedNumbers.size() - 1]
	while (begin < end) {
		int mid = (begin+end)/2
		(mid == sortedNumbers[mid])?(begin = mid + 1):(end = begin)
	}
	begin
}
assert missingNumber([0,1,3,4]) == 2

Csaba Okrona replied on Thu, 2013/02/28 - 8:57am

arr = [1,2,3,5,6,7]
correct_arr = (1..7).to_a
p correct_arr-arr #=> [4]

Régis Décamps replied on Thu, 2013/02/28 - 9:02am in response to: Vijay Nathani

Wait a minute... You need some indication during a binary search (you need to know whether the node you are looking for is smaller/bigger than the node you are currently looking at). You don't have this information when you are looking for a missing number.

Maybe you can explain a little more what you have in mind, because I'm probably missing something.

Vijay Nathani replied on Thu, 2013/02/28 - 9:04am in response to: Régis Décamps

I added Groovy solution to my previous answer.

Régis Décamps replied on Thu, 2013/02/28 - 9:10am in response to: Ajinkya Vaze

I like your implentation with the expected sum of numbers.

Régis Décamps replied on Thu, 2013/02/28 - 9:15am in response to: Vijay Nathani

I don't know Groovy, but if I read correctly, I suggest you add this unit test assert missingNumber([0,2,3,4]) == 1 You'll see your approach is wrong. I don't think one can beat O(n)

Vijay Nathani replied on Thu, 2013/02/28 - 10:09am in response to: Régis Décamps

There was a bug in my previous program. Instead of 

end = begin

it should be

end = mid.

But the logic is correct and peformance is O(log n). The corrected groovy program is

def missingNumber(def sortedNumbers) {
	def (begin, end) = [0, sortedNumbers.size() - 1]
	while (begin < end) {
		int mid = (begin+end)/2
		(mid == sortedNumbers[mid])?(begin = mid + 1):(end = mid)
	}
	begin
}
assert missingNumber([0,2,3,4]) == 1

Prasoon Kumar replied on Thu, 2013/02/28 - 11:02am

 The following PHP program will do it in O(n) vs O(log(n)) suggested above.

<?php

$input=array(0,1,2,4,5,6,7);
$n=7;
$expectedSum=($n*($n+1))/2;

$sum=0;
foreach($inputas$num)
$sum+=$num;

echo'Missing Number is:'.($expectedSum-$sum);
?>

Prasoon Kumar

Earnest Dyke replied on Thu, 2013/02/28 - 12:58pm

	@Test
	public void missingNumber() {
		Assert.assertEquals(3,
				findMissingNumber(new int[] { 0, 1, 2, 4, 5, 6 }));
		Assert.assertEquals(3, findMissingNumber(new int[] { 0, 1, 2, 4, 5, 6,
				7 }));

		Assert.assertEquals(71, findMissingNumber(new int[] { 67, 68, 69, 70,
				72 }));
		Assert.assertEquals(71, findMissingNumber(new int[] { 67, 68, 69, 70,
				72, 73 }));
	}

	private int findMissingNumber(int[] numbers) {
		// Even number of entries?
		int n = numbers[numbers.length - 1], a = numbers[0];
		int expected = (n * (n + 1) / 2);
		expected -= (a * (a + 1) / 2);
		int actual = 0;
		for (int i = 0; i < numbers.length; i++) {
			actual += numbers[i];
		}
		return expected - actual + a;
	}

Ajinkya Vaze replied on Fri, 2013/03/01 - 3:04am in response to: Vijay Nathani

When we are doing binary search we need some key....what is the search key here?

Vijay Nathani replied on Fri, 2013/03/01 - 3:40am in response to: Ajinkya Vaze

Array is sorted. 

Read my groovy program.

Remigio Di Muzio replied on Sat, 2013/03/02 - 3:07am in response to: Régis Décamps

Would be better to ponder before asserting anything dogmatically. Vijay Nathany's solution is optimal and the explanation of his algorithm lies in the fact that the numbers are sorted and are exactly those from 0 to n, so each number must be equal to its corresponding index in the array. Having to find the first occurrence of a number not equal to its index, we can use this invariant:at any given position, if the number at that position is equal to its index, the missing number is greater than the current one, otherwise is less, so the optimal average case solution is the O(log n) binary search algorithm.That is still valid for sequences starting with an arbitrary m, we just need to compare each value with its index + m.

Ajinkya Vaze replied on Sat, 2013/03/02 - 6:02am in response to: Vijay Nathani

I understood your solution now and its definitely the optimal one....Thanks Remigio Di Muzio for explaination. I was also thinking on similar lines, to use array index to find the missing number but never thought of doing it using binary search.

Daniel Sobral replied on Wed, 2013/03/06 - 10:26am

Easy solution (not efficient) in Scala (btw, when will we get syntax highlighting for it?):

def findMissing(a: Array[Int]): Option[Int] =
  (a sliding 2 collect { 
    case Array(a, b) if a + 1 != b => a + 1
  }).toStream.headOption

Sennen Ekouaghe replied on Wed, 2013/03/06 - 5:30pm

public class MissingNumberDetector {
    public static int getMissingNumber(int[] intArray) {
        return getMissingNumber(intArray, 0, intArray.length - 1);
    }

    private static int getMissingNumber(int[] intArray, int lowerBound, int upperBound) {
        if (lowerBound == upperBound) {
            return intArray[lowerBound] - 1;
        }
        int middle = (upperBound - lowerBound) / 2;
        if (middle == 0) {
            return intArray[upperBound] - intArray[lowerBound] == 1 ?
                   intArray[lowerBound] - 1 :
                   intArray[upperBound] - 1;
        }
        boolean completeLowerArray = intArray[lowerBound + middle] - intArray[lowerBound] == middle;
        if (completeLowerArray) {
            return getMissingNumber(intArray, lowerBound + middle + 1, upperBound);
        } else {
            return getMissingNumber(intArray, lowerBound, lowerBound + middle);
        }

    }
}

Sennen Ekouaghe replied on Wed, 2013/03/06 - 5:52pm in response to: Sennen Ekouaghe

Tested on [m,n] intervals with m >= 0 for arrays composed with distinct numbers.

Régis Décamps replied on Fri, 2013/03/08 - 6:36am in response to: Remigio Di Muzio

 Yes, thanks for the explanation. The trick was to compare the number with its index indeed. It's pretty clear now.

Abhilash Ponnachan replied on Sat, 2013/03/16 - 10:00am

Here is a Haskell hack :

let missing ns = last ns * (last ns + 1) / 2 - (sum ns)

Bob Beechey replied on Sat, 2013/03/30 - 10:27pm

Python hack:

 

set(range(1,myList[-1]+1)).difference(set(myList))


 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.