Thursday Code Puzzler: Find The Missing Number

//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;
	}

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

I added Groovy solution to my previous answer.

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)

 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

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

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.

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

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);
        }

    }
}

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

Python hack:

 

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