We pay for user submitted tutorials and articles that we publish. Anyone can send in a contribution

Learn More-
## Recent Posts

## Editor Pics

## Tags

.Net AJAX alexa Array ASP.Net ASP.NET MVC Binding blog stats C# challenge Class Code Controller DataTemplate earnings Event Free Interface JavaScript job interview jQuery LINQ List MVC page views Posts problem programming question RSS Shortcuts Silverlight Software SQL stats string Tool Traffic visits Visual Studio Web Window WPF Xaml Xml

By Shahar Y

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:**

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 :

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

Copyright © 2012 Dev102.com

Breeze : Designed by Amit Raz and Nitzan Kupererd

AlexSaid 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.

David PollSaid 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;

}

Michael MrozekSaid 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;

}

Michael MrozekSaid on June 30, 2008 :

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

Mark RSaid 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).

OJSaid 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!

Edward ShenSaid 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.

kenSaid on July 1, 2008 :

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

Carl AndersonSaid 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)).

Thaison LamSaid 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);

}

ShailendraSaid on July 1, 2008 :

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

Simon Ask UlsnesSaid 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

pavan kumarSaid 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

Kirill SorokinSaid 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).

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

Stephen BurtonSaid 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);

}

}

Poul Foged NielsenSaid 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();

configuratorSaid 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!

Micha? BendowskiSaid 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).

Ivan GrassoSaid on July 1, 2008 :

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

Complexity O(n)

Marius KlimantaviciusSaid 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.

thebolSaid 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)

steve_barhamSaid 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;

Shams MahmoodSaid 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;

}

Shams MahmoodSaid 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;

}

Samuel WilliamsSaid 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}”

Samuel WilliamsSaid on July 1, 2008 :

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

Shai OnSaid 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 :]

Sebastian USaid 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).

Tim CSaid 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.

HegiSaid 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:)

HegiSaid 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:)

NathanLaanSaid 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;

}

Guy GervaisSaid 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.

ValeraSaid 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))

antonSaid 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;

}

MoriSaid 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).

Jon von GillernSaid on July 1, 2008 :

I enjoy doing these, keep up the good work!

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

Stephen GoldbaumSaid 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

}

kranthiSaid on July 1, 2008 :

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

ZagNutSaid 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;

}

Angelo vd SijptSaid 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.

James CurranSaid on July 1, 2008 :

My solution:

http://honestillusion.com/blogs/blog_0/archive/2008/07/01/dev102-s-challenge-10-the-missing-number.aspx

krzysztof krejaSaid 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).

ASSaid 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.

LukeSaid 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).

Richard VasquezSaid 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.

Christof JansSaid on July 2, 2008 :

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

//Complexity = O(N)

Bruno BorgesSaid 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;

}

}

PavelSaid 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.

RandoomSaid on July 2, 2008 :

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

that’s n+1 numbers, not n

Luca GiurinaSaid 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…

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

Memory allocated is one int…

Bye!

Ops… complexity… O(n).

Josh BjornsonSaid 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;

}

}

KimmenSaid 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

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

Heiko HatzfeldSaid on July 2, 2008 :

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

Shahar YSaid on July 2, 2008 :

Hi Heiko,

Yes, you are allowed to do it.

Kris WarkentinSaid 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;

clegSaid 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

RandoomSaid on July 2, 2008 :

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

grigriSaid 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+>+<>+>>+>+

<<<>>>[<<<>>>-]<[<>>+>+<<<>>>[<<<>>>-]<[<>-]<-]

+<–]<>,————————————————[->-<]<>>++++++++++++++++++++++++++++++++++++++++++++++++.

AustinianSaid 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;

}

JohnSaid 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)

MartinSaid 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

Jesus DeLaTorreSaid 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

Hugh BrownSaid 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)

MichaelSaid 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;

}

Tim KingtonSaid 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.

Chris JobsonSaid 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.

JJSaid 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.

st0leSaid 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…

Heiko HatzfeldSaid 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

Guido DomeniciSaid 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;

Michael DikmanSaid 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;

}

}

Michael DikmanSaid 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

Frank DSaid 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…

Heiko HatzfeldSaid 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

Jesus DeLaTorreSaid on July 7, 2008 :

Yeah good thing I mentioned this

Heiko HatzfeldSaid 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

SSSaid 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;

}

Jesus DeLaTorreSaid 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.

Soumen SarkarSaid 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;

}

Heiko HatzfeldSaid on July 21, 2008 :

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

Best performance time and memory wise…

NabeelSaid 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 ????

Shams MahmoodSaid 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)

gebbSaid 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).

usman Arshad KurdSaid 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;

}