Hey all!

Its time for a new Challenge. But before that, last weeks answer. Well the answer could have been summed up by saying just traverse in reverse and return the second node . There were a few interesting answers among them Jonathan Gilbert’s who was the first to answer correctly:

This seems pretty simple to me. An in-order traversal can be reversed by simply following the right child first and the left child last. This produces a mirror-image. In this mirror image, the second-to-last from a regular traversal becomes the second item found. Thus, carrying a small amount of state with us so we know when to stop and return with what we’ve got:

class TreeNode
{
public int Value;
public TreeNode LeftChild, RightChild;

public TreeNode FindSecondToLastInOrder()
{
int skip = 1;

return find_second_to_last(ref skip);
}

private TreeNode find_second_to_last(ref int skip)
{
// Check the right child, if we have one.
if (RightChild != null)
{
TreeNode ret = RightChild.find_second_to_last(ref skip);

// If we’ve got something, skip went to 0 within the right child.
if (ret != null)
return ret;
}

// We’re yielding a node. Normally this would return it to some
// external consumer, but in this case, we simply count this node
// and return it if we’ve reached the desired count.
if (skip == 0)
return this;

skip–;

// Check the left child, if we have one.
if (LeftChild != null)
return LeftChild.find_second_to_last(ref skip);

// If we weren’t the last node in the in-order traversal and we
// don’t have a left child, return null to continue the hunt.
return null;
}
}

 

Ohter correct answers were from: Kris Warkentin, Michael Mrozek, Daniel Gray, Heiko Hatzfeld, Michael Dikman, Jason Kikel, Edward Shen, Bill Budge, Alex, Hugh Brown, Leppie, Configurator and Raj bhandari. Thanks to everyone, and now lets go to this weeks challenge.

This Wesek’s Question:

searchingNumbers This week question is pretty easy. Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. According to those rules, one of the numbers is missing and you are asked to provide the most efficient method to find that missing number. Notice that you can’t allocate another helper list, the amount of memory that you are allowed to allocate is O(1). Don’t forget to mention the complexity of your algorithm…

As always you may post the solution in your blog or comment. Comments will be approved next week.

Good luck

Tags :

89 Responses to “A Programming Job Interview Challenge #10 – The Missing Number”


  1. Alex

    Said on June 30, 2008 :

    Here’s an O(N) solution:

    Have one variable that stores the sum of all the values. Iterate through the list to add all numbers to the variable, which for simplicity I will call “listSum”.

    Now, take the theoretical sum of all numbers between 1…n+1: This can be computed in O(1), as the sum of numbers up to N is n(n+1)/2: So for numbers up to n+1, it’d be (n+1)(n+2)/2 (for instance, if the array is of size 9, we’d do 10*(11)/2, or a theoretical sum of 55). Call this sum “allSum”.

    The missing number will be the result of computing “allSum – listSum”.

    O(N)complexity, with only two tracking variables.

  2. David Poll

    Said on June 30, 2008 :

    I have an O(n) solution that takes O(1) space.

    public int FindMissingNumber(int[] nums)
    {
    int total = (n + 1) * (n + 2) / 2;
    foreach(int i : nums)
    total -= i;
    return total;
    }

  3. Michael Mrozek

    Said on June 30, 2008 :

    Add up all the numbers in the list and subtract the sum from the sum of all the numbers between 1 and n+1 (quickly found as ((n+1)(n+2))/2)

    int findMissing(int n, int arr []) {
    int count = ((n+1) * (n+2)) >> 1;
    while(n–) count -= arr[n];
    return count;
    }

  4. Michael Mrozek

    Said on June 30, 2008 :

    Oh, forgot the complexity on my last post: O(n)

  5. Mark R

    Said on June 30, 2008 :

    You’re right, this one’s easy.

    The sum of all numbers 1 to x is x*(x+1)/2. So, go through the entire list and keep a running total and the count (n); when you’re done, subtract the total from (n+1)*(n+2)/2 and that’s your missing number. The complexity of this solution is O(n).

  6. OJ

    Said on June 30, 2008 :

    First you’d sum all the numbers that are in the list. Then determine the sum of the numbers from 1 to N+1 using the generic formula “sum = (n+1)*n/2″ (remembering to use n+1, not n). Subtract the former from the latter, and you have the answer. Algo is O(n) I believe.

    Psuedo-code:
    int[] list = {..};
    int n = list.Length;
    missingNumber = (n+2)*(n+1)/2 – sum(list);

    Cheers!

  7. Edward Shen

    Said on June 30, 2008 :

    Keep subtracting numbers in the list from this number:
    ((N+1)(N+2)/2)

    The final number is your solution.

    O(n) as worst, best and avg runtime.

  8. ken

    Said on July 1, 2008 :

    x = sum(1 -> n+1) – sum( given list )

  9. Carl Anderson

    Said on July 1, 2008 :

    I would suggest using a method of bisection to hone in on a range that the missing value must fall. Thus, first traverse the list counting the number of values between low=1 and high=floor((n+1)/2) inclusive. If ct < high then the missing value is in this range, else it must be in range high+1 to n+1. Having halved the range, this can then be treated as a new problem with a new low and high. Repeat until high-low=2 (it is 2 because by this time both low and high will already have been computed and only high-1 will remain). The only variables needed for this algorithm are int low and int high. The complexity will be around O(n. log(n)).

  10. Thaison Lam

    Said on July 1, 2008 :

    We must assume numbers are integers since there is no solution for rational numbers.

    The missing number would be the difference of the sum of 1 to (n+1) and the sum of the array elements.

    Example, take n = 5 with 4 as the missing number:

    Sum of all numbers is 21:
    [1, 2, 3, 4, 5, 6] => 21
    Sum of array (with missing number = 4) is 17:
    [1, 2, 3, 5, 6] => sum is 17.
    Missing number x = 21 – 17 => 4.

    Complexity is O(n)?

    example solution:

    int findMissingNumber(int arr[], int n)
    {
    int partial, total = 0;
    for( int i = 0; i < n; ++i)
    {
    partial += arr[i];
    total += i + 1;
    }
    return (total – partial);
    }

  11. Shailendra

    Said on July 1, 2008 :

    (n+1)(n+2)/2 – (sum of all numbers in the list)

  12. Simon Ask Ulsnes

    Said on July 1, 2008 :

    Easy, just sum the elements and sum up the range 1..n+1, and subtract the two.

    This has running time of O(n).

    Here’s a quick Ruby implementation:

    [code]
    n = 100

    elements = (1..n+1).to_a

    missing = elements.delete_at(rand(elements.length))

    puts "Actually Missing: #{missing}"

    sum_range = 0
    for i in (1..n+1) do
    sum_range += i
    end

    sum_elements = 0
    for i in elements
    sum_elements += i
    end

    puts "Found Missing: #{sum_range - sum_elements}"
    [/code]

    (not sure about the formatting here, feel free to fix it)

    - Simon

  13. pavan kumar

    Said on July 1, 2008 :

    1: find sum of 1..n+1= (n+1)*n/2= S1 (O(1))
    2: Sum of each elment of the List =S2 (O(n)
    Missing Element = S1-S2

  14. Kirill Sorokin

    Said on July 1, 2008 :

    We need to sum the elements in the list. Then ((n+1)(n+2)/2 – sum) will give the number we’re looking for. As for the complexity, I guess it’s O(n).

  15. Florian K.

    Said on July 1, 2008 :

    Shouldn’t it be:
    sum up all numbers O(n) and O(1) store as sum_1

    calculate sum of the m:=n+1 first numbers with m*(m+1)/2 as store as sum_2

    Calculate difference: missing_number:=sum_2-sum_1

  16. Stephen Burton

    Said on July 1, 2008 :

    With no error checking ( or much of anything else for that matter) how about this, or have I totally misunderstood the question.

    package javaapplication1;

    public class Main {

    public static void main(String[] args) {
    int sum = 0;
    for( String a : args) {
    sum += Integer.decode(a);
    }
    int n = args.length;
    int expected = (n+1)*(n+2)/2;
    int missing = expected – sum;
    System.out.println(“Missing number = ” + missing);
    }

    }

  17. Poul Foged Nielsen

    Said on July 1, 2008 :

    Here’s one suggestion – there may be simpler ways of calculating the total of all numbers …

    (code is ready to execute in LINQpad)

    //The list of numbers
    var numbers = new byte[] {3, 2, 1, 5};

    // Calculate sum of all numbers, including the potential missing number
    var total = Enumerable.Range(1, numbers.Length + 1).Sum(x => x);

    // Loop over the numbers subtracting them from the total, remaining should be the missing number
    foreach(int num in numbers)
    total -= num;

    // Output the missing number
    total.Dump();

  18. configurator

    Said on July 1, 2008 :

    Clearly, we can’t efficiently search for every number through the entire list – that would be O(n^2).
    The most efficient way I could think of is to do an in-place sort (in place mergesort or heapsort), then go through the list once to find the missing number.
    The algorithm uses O(1) memory allocation and has an O(n log n) execution time.

    findmissing(l) {
    Sort(l);
    for (int i = 0; ; i++)
    if (l.Length <= i || l[i] != i + 1)
    return i;
    }

    Simple as that!

  19. Micha? Bendowski

    Said on July 1, 2008 :

    You can easily calculate the sum of numbers from 1 to n+1 (Gauss did it when he was 10 years old). Now just sum the numbers in the list (the result obviously will be smaller than the first sum) and see what is the missing number.

    It’s O(n).

  20. Ivan Grasso

    Said on July 1, 2008 :

    ((n+1)*(n+2)/2) – SUM ( all numbers) = magic number…

    Complexity O(n)

  21. Marius Klimantavicius

    Said on July 1, 2008 :

    I’d say calculate sum of 1..n+1 sequence (if I’m not mistaken that would be sumCalculated=((1+(n+1))/2)*(n+1)), this requires O(1) operations (or we can simply run loop, then complexity would be O(n)).
    Sum items of the given list (for example
    int sumReal = 0; for(int i=1;i<=n;i++) sumReal+=list[i];) we need O(n) operations.
    Finally the answer is sumCalculated – sumReal.
    Final algorithm complexity would be O(n) for operations, O(1) for memory as we allocate only two fixed size variables (I don’t count the list itself).
    Can’t think of any better now.

  22. thebol

    Said on July 1, 2008 :

    def getIntNotIn(int n, int[] listOfI) {
    def n1 = n +1;
    def totalSum = ((n1) * (n1 + 1)) / 2

    def sumOfList = listOfI.inject(0) {res, it -> res +=it}

    return totalSum – sumOfList
    }

    this is Groovy code(but i don’t compile it)
    the complexity is O(n)

  23. steve_barham

    Said on July 1, 2008 :

    Classic – sum the list, calculate the expected sum for a range of size n from (1..n+1), then subtract the actual sum to find the missing value.

    Order of efficiency is O(N). Two variables needed if you assume that you don’t know / can’t derive the size of the list without counting as you iterate. Simple Java solution:

    int sum = 0;
    int count = 1;
    int[] numbers = { 3, 2, 10, 1, 5, 7, 8, 6, 9 };

    for (int number : numbers) {
    sum += number;
    count++;
    }

    int expected = (int) (0.5 * count * (count + 1));
    int missing = expected – sum;

  24. Shams Mahmood

    Said on July 1, 2008 :

    This seems a problem that can be solved using arithmetic progression. First we find the sum of number from 1 to (n + 1). Then we need to deduct the each value in the List from this sum. The remaining value from the sum is the missing number.

    int findMissing(List pInput, int n) {

    int eSum = (int)(((n + 1) * (n + 2)) / 2);
    for (int i = 0; i < pInput.size(); i++) {
    eSum -= pInput.get(i);
    }
    return eSum;
    }

  25. Shams Mahmood

    Said on July 1, 2008 :

    This seems a problem that can be solved using arithmetic progression. First we find the sum of number from 1 to (n + 1). Then we need to deduct the each value in the List from this sum. The remaining value from the sum is the missing number.

    This solution has a time complexity of O(n), space complexity is O(1).

    int findMissing(List pInput, int n) {

    int eSum = (int)(((n + 1) * (n + 2)) / 2);
    for (int i = 0; i < pInput.size(); i++) {
    eSum -= pInput.get(i);
    }
    return eSum;
    }

  26. Samuel Williams

    Said on July 1, 2008 :

    This is pretty easy question!! (Touch wood ^_^)

    #!/usr/bin/env ruby

    class Array

    def randomize
    duplicated_original, new_array = self.dup, self.class.new
    new_array <<
    duplicated_original.slice!(rand(duplicated_original.size)) until
    new_array.size.eql?(self.size)
    new_array
    end

    def randomize!
    self.replace(randomize)
    end

    end

    n = 10
    nums = (1..n+1).to_a.randomize
    puts “Number missing: #{nums.pop}”

    n1 = n + 1
    total = (n1 * (2 + n)) / 2

    sum = 0

    nums.each do |v, i|
    sum += v
    end

    puts “Sum: #{sum}”
    puts “Total: #{total}”
    puts “Difference: #{total – sum}”

  27. Samuel Williams

    Said on July 1, 2008 :

    Sorry, the complexity of the algorithm is O(N).

  28. Shai On

    Said on July 1, 2008 :

    Just sum everything up while reading from the input, and subtract (n+1) by the sum. You’ll receive the missing number and it’s complexity is, well, the same complexity in which you read n items from input, only need 1 variable, etc :]

  29. Sebastian U

    Said on July 1, 2008 :

    The missing number is the difference between the expected sum ( (n+1)(n+2)/2 ; O(1) ) and the actual sum of the list (O(n), e.g. Enumerable.Sum). The overall complexity is O(n).

  30. Tim C

    Said on July 1, 2008 :

    int whatIShouldHave = N * (N + 1) / 2;
    int whatIHave = theList.Sum();
    int theMissing = whatIShouldHave – whatIHave;

    O(N) which is the time it takes to call theList.Sum.

  31. Hegi

    Said on July 1, 2008 :

    Simple:
    sum = n(n+1)/2 (sum of all elements of arithmetic sequence from 0 to n+1).

    foreach (int element in list)
    sum -= element;

    missingElement = sum;

    That’s it, I presume.
    We can’t go lower then O(n) time complexity, cause list isn’t sorted. This solution uses exactly one additional variable so I figure I’ve met O(1) space complexity requirment:)

  32. Hegi

    Said on July 1, 2008 :

    Sorry if this is a double post, but my window crashed and I realy don;t know whether it submitted this comment.

    Simple:
    sum = n(n+1)/2 (sum of all elements of arithmetic sequence from 0 to n+1).

    foreach (int element in list)
    sum -= element;

    missingElement = sum;

    That’s it, I presume.
    We can’t go lower then O(n) time complexity, cause list isn’t sorted. This solution uses exactly one additional variable so I figure I’ve met O(1) space complexity requirment:)

  33. NathanLaan

    Said on July 1, 2008 :

    Here is an O(n) solution: Iterate through the list, adding up the items in the list, as well as the indexes into the list, including one extra index at the end. Subtracting the sum of the items in the list from the sum of the list indexes gives the missing value. Note that the code below is assuming a programming language with zero-based array indexes.

    int FindMissing(int[] list)
    {
    int actualTotal = 0;
    int expectedTotal = 0;
    int count;
    for(count=0;count<list.Length;count++)
    {
    expectedTotal += (count+1);
    actualTotal += list[count];
    }
    expectedTotal += (count+1);
    return expectedTotal – actualTotal;
    }

  34. Guy Gervais

    Said on July 1, 2008 :

    Considering that the sum of numbers 1..n can be expressed as n*(n+1)/2, then we simply count the numbers as we sum them up; calculate the expected value (of final count + 1, for the missing number) and substract our current sum to get the missing number.

  35. Valera

    Said on July 1, 2008 :

    Apply qsort, then check (n[i] == n[i+1] + 1) rule
    or include this check into qsort, so complicity of this algorithm is about O(nlog(n))

  36. anton

    Said on July 1, 2008 :

    /*
    * In O(n), with memory allocation in O(1)
    * (two integers).
    *
    * We take advantage of Gauss’ formula :
    * the input parameter (numbers) is the sum
    * from 1 to n+1, minus some integer p, i.e.
    * sum(numbers) = (n+1)(n+2)/2 – p, hence
    * p = (n+1)(n+2)/2 – sum(numbers).
    */
    int find_missing(int[] numbers) {
    // mem. alloc. — O(1)
    int sum_if_they_were_all_there = (n+1)(n+2)/2; // O(1)
    int actual_sum = 0;

    // compute the sum — O(n)
    for (int i : numbers) actual_sum += i;

    return sum_if_they_were_all_there – actual_sum;
    }

  37. Mori

    Said on July 1, 2008 :

    Calculate the total of the first n + 1 integers. This is your stored value. Iterate through the list, subtracting each number from the total. The remaining value is the missing number and this algorithm is O(n).

  38. Jon von Gillern

    Said on July 1, 2008 :

    I enjoy doing these, keep up the good work!

    http://www.vonsharp.net/ProgrammingJobInterviewChallenge10Answer.aspx

  39. Stephen Goldbaum

    Said on July 1, 2008 :

    In Scala (Time is O(n):

    def missing(list:List[Int]) = {
    val len = list.length+1
    val total = ((len*len)+len) / 2
    var sum = 0
    for(i <- list) sum += i
    total – sum
    }

  40. kranthi

    Said on July 1, 2008 :

    sum(1…n+1) – sum(unordered_list)

  41. ZagNut

    Said on July 1, 2008 :

    // a C# method:

    public int FindMissing(List theList)
    {
    int list_count = theList.Count;
    if (list_count == 0)
    throw new Exception(“The list has no members yet”);
    int missingnumber = ((list_count + 1) * (list_count + 2)) / 2;
    foreach (int i in theList)
    if ((i list_count + 1))
    throw new Exception(“The list contains invalid entries for this question.”);
    else
    missingnumber -= i;
    return missingnumber;
    }

  42. Angelo vd Sijpt

    Said on July 1, 2008 :

    My solution:

    public int findMissingNumber(int[] numbers) {
    int missing = numbers.length + 1;
    for (int i = 0; i < numbers.length; i++) {
    missing += (i + 1) – numbers[i];
    }
    return missing;
    }

    This solution works by combining two steps: one, it finds out what the total sum of the full array (including the missing number) would be, and two, it sums up all numbers in the passed array. The difference between these two totals is the missing number.
    These two steps are combined into the ‘+=’ step, meaning the solution only needs one loop.

    The complexity of the solution is O(n), and the amount of extra memory allocated is two ints.

  43. James Curran

    Said on July 1, 2008 :

  44. krzysztof kreja

    Said on July 1, 2008 :

    The sum of n+1 successive elements from 1 till n+1 (arithmetic progression) is known: (1+(n+1))*(n+1)/2. That means that we only need to add all the elements from the unordered list to each other and subtract the result from the sum above. The result is the solution and we get it in O(n).

  45. AS

    Said on July 1, 2008 :

    IIRC the sum for i from 1 to n is n * (n+1) /2, so, (n+1)*(n+2)/2 minus the sum of the given list should give the desired response with a fixed memory use and a linear time.

  46. Luke

    Said on July 1, 2008 :

    If I have understood correctly you can do it this way: use mathematical equation for a sum of numbers from 1 to n+1 (it will be ((n+1)(n+2))/2 if I remeber correctly) then iterate through array and subtract each of the element of the array from the sum counted before. Here is missing number. Algorithm will be O(n).

  47. Richard Vasquez

    Said on July 2, 2008 :

    The sum S of all the numbers from 1 to n + 1 (including our missing M) is going to be:

    ((1 + n + 1) * (n + 1)) / 2
    [I like parenthesis]

    If you iterate through all the numbers, adding to an initial 0 resulting in some sum N, then the equation to find our missing number is:

    M = S – N.

  48. Christof Jans

    Said on July 2, 2008 :

    int missingValue = Enumerable.Range(1, N+1).Sum() – inputlist.Sum();

    //Complexity = O(N)

  49. Bruno Borges

    Said on July 2, 2008 :

    I’m not sure if a broke some rule, but here goes my implementation :-)

    The idea is to sort all members (this is the most time expensive part). Then the program just check for the even-odd comparison of each side (lower and higher numbers), as it should be an arithm. progression with r = 1. Like in this example:

    N(10) = {4, 3, 1, 8, 2, 6, 9, 5, 10, 11}
    Sorted: {1, 2, 3, 4, 5, 6, 8, 9, 10, 11}

    Comparisons:
    1 – 11 = odd
    2 – 10 = even
    3 – 9 = odd
    4 – 8 = even
    5 – 6 = 6 is even, should be odd

    I did a test with a random list with N(8651997) and it took:
    * Sorting time : 2218ms
    * Time to search: 16ms (even-odd comparison)
    * Total time : 2234ms

    So, I couldn’t find a method to catch the missing number without sorting the list. But the small algorithm to compare even-odd did the job fairly enough. :-)

    I tought that I could search for it while sorting, but sorting algorithms are hard to pick and those that could give me a small piece of sorted numbers to test if the missing number was there, were too slow with big lists like the one above.

    Regards,
    Bruno


    package com.dev102.challenge10;

    import java.util.Arrays;

    public class MissingNumber implements IMissingNumber {

    @Override
    public int findMissingNumber(int[] numbers) {
    Arrays.sort(numbers);
    int half = numbers.length / 2;
    int missing = half + 1;
    boolean lastEven = true;

    for (int i = 0; i < half; i++) {
    int num = numbers[i];
    if (equalEven(num, lastEven)) {
    missing = num – 1;
    break;
    }

    // check the other side
    int otherSide = numbers[half * 2 - i - 1];
    if (equalEven(otherSide, lastEven)) {
    missing = otherSide + 1;
    break;
    }

    lastEven = !lastEven;
    }

    return missing;
    }

    private boolean equalEven(int number, boolean lastEven) {
    return ((number & 1) == 0) == lastEven;
    }

    }

  50. Pavel

    Said on July 2, 2008 :

    (n+2)(n+1)/2 – sum(list) is the missing number.

    Since numbers are unique and only one is missing adding it would mean that we have all the numbers and sum of numbers 1 to n+1 is (n+1)*(n+2)/2.

    Complexty is O(n) since that’s what summing costs. We can’t get any better than that since we have to at least look at every number to find the missing one.

  51. Randoom

    Said on July 2, 2008 :

    >>> list of n numbers ranging from 1 to n+1

    that’s n+1 numbers, not n

  52. Luca Giurina

    Said on July 2, 2008 :

    The sum of the firsts n+1 numbers is (n+1)*((n+1)+1)/2. Right?

    Allocate one int (as “s”), score the list numbers, sum all ones, and put the result in “s”.

    The number we will searching for is ((n+1)*(n+2)/2)- “s”. I think… :-P

    “s” = (((n+1)*(n+2))/2) – “s”

    Memory allocated is one int…

    Bye!

    Ops… complexity… O(n).

  53. Josh Bjornson

    Said on July 2, 2008 :

    /**
    * This solution has O(n) in complexity as it needs to iterate over the unsorted list
    * of numbers to calculate the sum of the list and the minimum and maximum values in the list.
    * The missing number from the sequence is the difference between the expected sum
    * and the actual sum. The expected sum is defined as the sum of the divergent series to the
    * maximum value in the list minus the sum of the divergent series to the minimum value in the list.
    * The order of the numbers in the provided list has no effect on the results.
    *
    * @author Josh Bjornson
    *
    */
    public class MissingNumberInSequenceFinder {

    /**
    * Find the missing number in the unordered list of numbers that represents a sequence.
    * Sum up the values in the list and calculate how far off from the expected sum we are
    * (and that is the missing number).
    *
    * @return
    */
    public static int findMissingNumber(final int[] numbers) {
    int minValue = 0;
    int maxValue = 0;
    long sum = 0L;

    // collect the sum and remember the minimum and maximum values in the list so far
    for (int currentValue: numbers) {
    sum += currentValue;
    minValue = (currentValue maxValue) ? currentValue : maxValue;
    }

    // the missing number from the sequence should be the
    // difference between the expected sum and the actual sum
    long expectedSum = (calculateSeriesSum(maxValue) – calculateSeriesSum(minValue));
    return (int)(expectedSum – sum);
    }

    /**
    * Calculate the sum of the divergent series of numbers starting from 1
    * and incrementing (or decrementing) to n.
    * The formula for this calculation is: (n * (n + 1)) / 2 for positive numbers,
    * (n * (n – 1)) / 2 for negative numbers and 0 when n is equal to zero.
    *
    * @param n
    * @return the sum of the sequence 1 + 2 + … + n
    */
    public static long calculateSeriesSum(int n) {
    long sum = 0;
    if (n > 0) {
    sum = ((long)n * ((long)n + 1L)) / 2L;
    } else if (n < 0) {
    sum = ((long)n * ((long)n – 1L)) / 2L;
    } else {
    sum = 0;
    }
    return sum;
    }

    }

  54. Kimmen

    Said on July 2, 2008 :

    Choose an sorting algorithm which has O(1) memory complexity. I would probably choose “In place mergesort” which has the time complexity of O(n log n).

    Sort the unsorted list. Starting from the beginning, go through the list checking if sortedList[i] + 1 != sortedList[i+1]. When that statement is true, you have found your missing number. This has a time complexity of O(n), which means the total is O(n log n).

    The simplest solution is probably:
    for(int i = 1; i <= unsortedList.Count + 1; i++)
    {
    if(!unsortedList.Contains(i)) return i;

    }
    But that has a time complexity of O(n^2), but it’s simple! =D

  55. leppie

    Said on July 2, 2008 :

    Time complexity: O(n)
    Space complexity: O(1)

    Code speaks :)

    int[] l = { 4, 3, 2, 7, 1, 5 };
    int n = l.Length;

    int sum = 0;

    for (int i = 0; i < n; i++)
    {
    sum += l[i];
    }

    int missing = (int)( (n + 2) / 2.0 * (n + 1) – sum);

  56. Heiko Hatzfeld

    Said on July 2, 2008 :

    Are we allowed to change the order of the Elements in the input array?

  57. Shahar Y

    Said on July 2, 2008 :

    Hi Heiko,

    Yes, you are allowed to do it.

  58. Kris Warkentin

    Said on July 2, 2008 :

    The sum of 1 + 2 + … + (n + 1) is
    (n+1)*(n+2)/2

    Therefore the missing number is the sum of the numbers in the list minus the result of the above formula. ie.

    int missing;
    int expected = (n + 1) * (n + 2) / 2;
    int actual = 0;

    for(int i = 0 ; i < n ; i++)
    actual += numbers[i];

    missing = expected – actual;

  59. cleg

    Said on July 2, 2008 :

    It’s simple (if i understood ask properly).
    All we have to do – calculate sum of the elements we have (S1). Sum of all the numbers from 1 to n+1 easy calculated S2 = (1+n+1)*(n+1)/2

    So missing element is S2-S1

  60. Randoom

    Said on July 2, 2008 :

    missing# = (n+1)(n+2)/2 – sum(input)

  61. grigri

    Said on July 2, 2008 :

    Hi, just discovered this site – looks nice!

    Here’s my solution:

    If the number were present, we would have all the numbers 1..(1+n).

    By basic algebra, their sum would be ((1+n)*(2+n))/2.

    So the missing number is the above sum minus the sum of the numbers we do have; requiring a single pass.

    Complexity : O(n)
    Memory used : O(1)

    In c (no error checking):

    int missing_number(int n, int *numbers) {
    int total = ((n+1)*(n+2)) << 1;
    for (int i=0; i+>+<>+>>+>+
    <<<>>>[<<<>>>-]<[<>>+>+<<<>>>[<<<>>>-]<[<>-]<-]
    +<–]<>,————————————————[->-<]<>>++++++++++++++++++++++++++++++++++++++++++++++++.

  62. Austinian

    Said on July 2, 2008 :

    My solution involves calculating the sum of the numbers, were the list to be complete, and subtracting each of the numbers actually in the list from that. The result should be the missing number. This is O(n).

    Solution in Java…

    public int findMissing(int[] inputs) {
    int sum = ((inputs.length+1)*(inputs.length*2))/2;

    for(int i : inputs) {
    sum =- i;
    }

    return sum;

    }

  63. John

    Said on July 2, 2008 :

    Simple formula for this problem.

    ((n + 1) * (n+2)) / 2 – sum(elelment[1] …. element[n]) = X

    function int FindMissingNumber(List elements)
    {
    var sumOfNums = ((n + 1) * (n + 2)) / 2
    var sumOfElements = 0;
    for(var i = 0; i < elements.length; i++)
    sumOfElements += elements[i];

    return (sumOfNums – sumOfElements);
    }

    Memory Allocation: O(1)
    Complexity: O(n)

  64. Martin

    Said on July 2, 2008 :

    Hi,

    my solution is the difference between the arithmetic series of the n+1 elements and the sum of the actual elements in the input array.
    The complexity is linear: calculating the sum of the elements in the input array.
    The allocation of memory is constant: one variable initially stores the arithmetic series, the other variable stores the current sum of the elements in the input array on each iteration of the loop.

    This might be not the most efficient solution, but it’s the most obvious one I could think of. I’m looking forward to see the really most efficient solution ;)

    Cheers, Martin

  65. Jesus DeLaTorre

    Said on July 2, 2008 :

    As long as you dont get a buffer overflow, I will add all the numbers up and then subtract it from (n+1)((n+1)+1)/2 http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%C2%B7_%C2%B7_%C2%B7

  66. Hugh Brown

    Said on July 2, 2008 :

    If all the numbers 1..n were present, then they would sum to:
    n(n+1)/2
    but if some x is absent, then they will sum to:
    n(n+1)/2 – x
    So to determine which number is missing, subtract the sum of the series from the expected sum.

    This python code finds the missing number in the series named values:

    def test(values) :
    max_val = len(values) + 1
    expected_sum = max_val*(max_val + 1) / 2
    return expected_sum – sum(values)

  67. Michael

    Said on July 3, 2008 :

    This is easy task. Gauss solved it lot years ago. when in one step sum all numbers from 1 to 100.

    Missing number is sum for (1..n), which calculated as (n+1) * (n/2), minus sum of all elements in the list 1..n

    The next solution implemented on the perl with one specific case. For list3 will be nothing found, probably you except get 10 as missing number :), but I did not included this specific case.

    # finding missing number
    my @list1 = (1,2,3,4,5,6,8,9,10);
    my @list2 = (2,3,4,5,6,7,8,9,10);
    my @list3 = (1,2,3,4,5,6,7,8,9);
    my @list4 = (1,3);
    my @list5 = (1,2,4);

    print getMissingNumber(@list1), “\n”;
    print getMissingNumber(@list2), “\n”;
    print getMissingNumber(@list3), “\n”;
    print getMissingNumber(@list4), “\n”;
    print getMissingNumber(@list5), “\n”;

    sub getMissingNumber
    {
    local $max = 0;
    local $sum = 0;
    local $missingNumber = 0;

    foreach my $element (@_)
    {
    $sum += $element;
    $max = $max > $element ? $max : $element;
    }

    $requiredSum = ($max + 1) * $max / 2;

    return $requiredSum – $sum;

    }

  68. Tim Kington

    Said on July 3, 2008 :

    You can do it O(n) time and O(1) space by adding all of the numbers that do appear. Then n(n + 1) / 2 – total is the missing number.

  69. Chris Jobson

    Said on July 3, 2008 :

    int sum = 0;
    foreach (int i in the list)
    sum += i;
    missingNumber = ((n+1)*(n+2))/2 – sum;

    This uses the fact the sum of the numbers from 1 to n+1 is ((n+1)*(n+2))/2.

  70. JJ

    Said on July 3, 2008 :

    Here is my solution.

    Loop through all numbers in the array, adding the current value to an accumulator variable that is initialized to 0.
    subtract this number from (n+1) * n/2.
    This in O(n) in time.

  71. st0le

    Said on July 3, 2008 :

    s ? 0
    for i = 1 to n:
    s ? s + A[i]
    next i

    return ((n+1)*(n+2)/2) – s;

    oh, i’m sort of confused about the “n” or “n+1″ but i guess you understand the logic behind it…

  72. Heiko Hatzfeld

    Said on July 4, 2008 :

    If we are allowed to mess with the original input list, then this becomes a lot easier.

    We “just” have to sort the input, and then find a gap in the sorted list. We could improve this futher if we try do detect the gap while we are sorting already, and quit sorting if we detect the gap.
    Since we are restricted on the amount of memory we are allowed to use, we have to use some alternative sorting algorithems.

    We have to exclude the common sorting procedures like quicksort.

    I think the best pick would be something like an in place merge sort. But to be sure that we actually found the gap, we would have to complete the sort, so the runtime would allways be something like O(N log(N)) + time to find the gap

    The other alternative would be something like a selection sort. This alogithem would allow us to break eraly if we find a gap. But the downside on this would be the relative performannce of only O(N^2).

    You could also consider Heapsort which is O(N Log(N)), which would also allow you to break out of the sorting, and has the optimal time. (But the code is a little bit more complex)

    But I think the bester alternative would be investing in a new computer. You already had several problems due to memory constrains ;)

  73. Guido Domenici

    Said on July 4, 2008 :

    Well I have an O(n) solution with O(1) storage. You calculate the sum of all integers between 1 and n+1 (which is O(1) with the Gauss formula ((n+1)*(n+2))/2), and then you calculate the actual total by looping over the array, which is O(n). The difference between these two quantities is is the missing number:

    int expectedTotal = ((N+1)*(N+2))/2;
    int runningTotal = 0;
    for (int ndx = 0; ndx < N; ndx++)
    {
    runningTotal += list[ndx];
    }

    int foundMissingNo = expectedTotal – runningTotal;

  74. Michael Dikman

    Said on July 5, 2008 :

    My solution:
    Run once on the array summing its values into a variable O(n) – runtime, O(1) memory.
    Then make a loop summing all numbers from N+1 to 1 into some other variable.
    Then substract second variable form the first one.

    int findMissing(int[] arr)
    {
    int sum = 0;
    for (int i=0; i<arr.length; ++i)
    sum += arr[i];
    int neededSum = 0;
    for (int i=0; i<arr.length + 1; ++i)
    neededSum += i;
    return neededSum – sum;
    }

    }

  75. Michael Dikman

    Said on July 5, 2008 :

    Upgrade to my previous algorothm.
    The second loop is not needed, can use equation for sum of arithmetic series:
    neededSum = ((N+1)*(N+2))/2

  76. Frank D

    Said on July 7, 2008 :

    The sum of the input array would be (n+2)*(n+1)/2 if no number was missing.

    So calculate the actual sum of the numbers in the array and subtract from the above result.

    The difference should be the missing number.

    No need for sorting or anything…

  77. Heiko Hatzfeld

    Said on July 7, 2008 :

    I have to “nitpick” since I provided the “wrong” solution…

    The “smart” solution is only valid for small inputs. It will fail with an overflow, if the array gets to big (depending on the size of int if your favorite language ) So you would have to allocate O(2) memory (long) to solve this problem for all possible inputs. You could only process an array of about 65534 (Unsigned)Ints, while the sorting solution will be able to handle any size of input array ;)

    Yes I know i am nitpicking… But its the only way in which i can try to sell my answer as correct :D

  78. Jesus DeLaTorre

    Said on July 7, 2008 :

    Yeah good thing I mentioned this :P

  79. Heiko Hatzfeld

    Said on July 8, 2008 :

    I read the comments this time, and it seems like you are the only one who was aware of that problem ;)

  80. SS

    Said on July 18, 2008 :

    I have improved method_2 over method_1. I think in method_2 there is less chance of integer overflow.

    public static int method_1(int [] sequence)
    {
    // this can overflow
    int allSum = ((sequence.length + 1) * (sequence.length + 2)) / 2;

    int seqSum = 0;
    for (int i = 0; i < sequence.length; ++i)
    {
    // this can overflow
    seqSum += sequence[i];
    }

    return allSum – seqSum;
    }

    /**
    * @param sequence : Sequence of length N Contains integers 1 to (N + 1)
    * with one number missing. The array is unsorted.
    *
    * @return The missing number
    */
    public static int method_2(int [] sequence)
    {
    int missingNum = sequence.length + 1;
    for (int i = 0; i < sequence.length; ++i)
    {
    missingNum += ((i+1) – sequence[i]);
    }

    return missingNum;
    }

  81. Jesus DeLaTorre

    Said on July 18, 2008 :

    Just because there is a less chance doesnt make the method better, there is still a chance of an overflow.

    I think a better and faster solution would be to use your method 1 and then check for an overflow before even computing. Since we know MAX_INT32 we can figure out the biggest number of N we can take and guarantee a nonoverflow.

    Now that I think about it does overflow really even matter? Unless N is so large that itself will overflow, you can still get the missing number since the “gap” between the expected computed total and the running total will still be there. You would just need a special case for when the computed total overflow and when the running gap didn’t.

    This can be taken care of by

    if(runningtotal > computedtotal)
    missingnumber = computedtotal + (MAXINT32 -runningtotal) + 1

    Again this would only work if N is not an overflow number by itself.

  82. Soumen Sarkar

    Said on July 20, 2008 :

    Reply to: Jesus DeLaTorre on Jul 18, 2008

    I agree with your statement: “Just because there is a less chance doesnt make the method better, there is still a chance of an overflow.”

    Hence I have provided a method which do NOT use any integer summing. Instead I use
    cumulative XOR to cancel out duplicates. Here is the third implementation:

    /**
    * @param sequence : Sequence of length N Contains integers 1 to (N + 1)
    * with one number missing. The array is unsorted.
    *
    * @return The missing number
    *
    * Algorithm: In this case we do not calculate any integer sum at all. We do cumulative XOR of all elements with index. Please note that N XOR N == 0. So all elements eventually cancel all index and last number standing after cumulative XOR is the missing number. For
    example consider the sequence [1] [2] [3] [?].
    So 1 XOR 1 == 0, 2 XOR 2 == 0, 3 XOR 3 == 0, so last number standing will be 4. It does not matter if numbers are permuted instead of being sorted.
    */

    public static int method_3(int [] intSeq)
    {
    int missingNum = intSeq.length + 1;
    for (int i = 0; i < intSeq.length; ++i)
    {
    missingNum ^= ((i+1) ^ intSeq[i]);
    }

    return missingNum;
    }

  83. Heiko Hatzfeld

    Said on July 21, 2008 :

    I like the XOr solution. Thats realy thinking outside of the box.

    Best performance time and memory wise…

  84. Nabeel

    Said on November 29, 2008 :

    This is a very easy question. Suppose intead of 1 number missing, there are two numbers missing. Then what will you do ????

  85. Shams Mahmood

    Said on November 30, 2008 :

    @Nabeel

    Sort the input data using pigeonhole sort = O(2n)
    Iterate through the elements in the pigeon hole array to report the empty holes as the missing elements = O(n)
    So overall done in O(3n) ;)

  86. gebb

    Said on March 7, 2011 :

    @Nabeel
    I will find the two missing numbers using the following formulae:
    i = 1/2 (-S + Sn + D)
    j = 1/2 (-S + Sn – D)
    where
    D = Sqrt[-2 Q + 2 Qn - S^2 + 2 S Sn - Sn^2]
    S — sum of all elements in the array;
    Q — sum of the squares of all elements.
    Sn = 1/2 n(n+1) — sum of an arithmetic progression.
    Qn = 1/6 n(1 + n)(1 + 2 n) — sum of the squares of an arithmetic progression.
    n — size of the array plus 2.

    This solution takes O(1) space and O(n) time (finding S and Q).

  87. usman Arshad Kurd

    Said on June 6, 2011 :

    public int FindMissingNumber(int[] nums)
    {
    int sum=0;
    int total = (n + 1) * (n + 2) / 2;
    for(int i=0;i<n;i++)
    sum+=num[i];
    total-=sum;
    return total;

    }

2 Trackback(s)

  1. Jul 1, 2008: The missing number » FSharp.it
  2. Jul 7, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #11 - SUMMING NUMBERS | Dev102.com

Post a Comment