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
2 Trackback(s)
- Jul 1, 2008: The missing number » FSharp.it
- Jul 7, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #11 - SUMMING NUMBERS | Dev102.com
Alex Said on Jun 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 Poll Said on Jun 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 Mrozek Said on Jun 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 Mrozek Said on Jun 30, 2008 :
Oh, forgot the complexity on my last post: O(n)
Mark R Said on Jun 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).
OJ Said on Jun 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 Shen Said on Jun 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.
ken Said on Jul 1, 2008 :
x = sum(1 -> n+1) - sum( given list )
Carl Anderson Said on Jul 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 Lam Said on Jul 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);
}
Shailendra Said on Jul 1, 2008 :
(n+1)(n+2)/2 - (sum of all numbers in the list)
Simon Ask Ulsnes Said on Jul 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 kumar Said on Jul 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 Sorokin Said on Jul 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 Jul 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 Burton Said on Jul 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 Nielsen Said on Jul 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();
configurator Said on Jul 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? Bendowski Said on Jul 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 Grasso Said on Jul 1, 2008 :
((n+1)*(n+2)/2) - SUM ( all numbers) = magic number…
Complexity O(n)
Marius Klimantavicius Said on Jul 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.
thebol Said on Jul 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_barham Said on Jul 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 Mahmood Said on Jul 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 Mahmood Said on Jul 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 Williams Said on Jul 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 Williams Said on Jul 1, 2008 :
Sorry, the complexity of the algorithm is O(N).
Shai On Said on Jul 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 U Said on Jul 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 C Said on Jul 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.
Hegi Said on Jul 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:)
Hegi Said on Jul 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:)
NathanLaan Said on Jul 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 Gervais Said on Jul 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.
Valera Said on Jul 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))
anton Said on Jul 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;
}
Mori Said on Jul 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 Gillern Said on Jul 1, 2008 :
I enjoy doing these, keep up the good work!
http://www.vonsharp.net/ProgrammingJobInterviewChallenge10Answer.aspx
Stephen Goldbaum Said on Jul 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
}
kranthi Said on Jul 1, 2008 :
sum(1…n+1) - sum(unordered_list)
ZagNut Said on Jul 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 Sijpt Said on Jul 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 Curran Said on Jul 1, 2008 :
My solution:
http://honestillusion.com/blogs/blog_0/archive/2008/07/01/dev102-s-challenge-10-the-missing-number.aspx
krzysztof kreja Said on Jul 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).
AS Said on Jul 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.
Luke Said on Jul 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 Vasquez Said on Jul 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 Jans Said on Jul 2, 2008 :
int missingValue = Enumerable.Range(1, N+1).Sum() - inputlist.Sum();
//Complexity = O(N)
Bruno Borges Said on Jul 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;
}
}
Pavel Said on Jul 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.
Randoom Said on Jul 2, 2008 :
>>> list of n numbers ranging from 1 to n+1
that’s n+1 numbers, not n
Luca Giurina Said on Jul 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 Bjornson Said on Jul 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;
}
}
Kimmen Said on Jul 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
leppie Said on Jul 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 Hatzfeld Said on Jul 2, 2008 :
Are we allowed to change the order of the Elements in the input array?
Shahar Y Said on Jul 2, 2008 :
Hi Heiko,
Yes, you are allowed to do it.
Kris Warkentin Said on Jul 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;
cleg Said on Jul 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
Randoom Said on Jul 2, 2008 :
missing# = (n+1)(n+2)/2 - sum(input)
grigri Said on Jul 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+>+<>+>>+>+
<<<>>>[<<<>>>-]<[<>>+>+<<<>>>[<<<>>>-]<[<>-]<-]
+<–]<>,————————————————[->-<]<>>++++++++++++++++++++++++++++++++++++++++++++++++.
Austinian Said on Jul 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;
}
John Said on Jul 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)
Martin Said on Jul 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 DeLaTorre Said on Jul 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 Brown Said on Jul 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)
Michael Said on Jul 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 Kington Said on Jul 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 Jobson Said on Jul 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.
JJ Said on Jul 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.
st0le Said on Jul 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 Hatzfeld Said on Jul 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 Domenici Said on Jul 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 Dikman Said on Jul 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 Dikman Said on Jul 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 D Said on Jul 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 Hatzfeld Said on Jul 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 DeLaTorre Said on Jul 7, 2008 :
Yeah good thing I mentioned this
Heiko Hatzfeld Said on Jul 8, 2008 :
I read the comments this time, and it seems like you are the only one who was aware of that problem
SS Said on Jul 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 DeLaTorre Said on Jul 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 Sarkar Said on Jul 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 Hatzfeld Said on Jul 21, 2008 :
I like the XOr solution. Thats realy thinking outside of the box.
Best performance time and memory wise…