Author |
Topic: Minimum non existing number (Read 4472 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Minimum non existing number
« on: Mar 26th, 2012, 12:06pm » |
 Quote  Modify
|
Given an unsorted array of integers, find the minimum of all positive integers that does not exist in the array.
For example,
[1,2,0] returns 3
[3,4,-1,1] returns 2
Can it be done inO(n) time and O(1) space?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #1 on: Mar 26th, 2012, 12:53pm » |
Quote Modify
|
Are the number in the array distinct?
Because if that's the case an O(n) time O(1) solution readily comes to mind. (Start by pivoting around 0 and discarding all number <= 0; Then repeatedly pick a pivot and check if the largest number in the 'small' equals the number of elements in it to see if there's one missing.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum non existing number
« Reply #2 on: Mar 27th, 2012, 2:00am » |
Quote Modify
|
If the array has size n, then the answer is between 1 and n+1. Just use an array of n booleans to check which ones are present.
PS: uh... but that wouldn't be O(n) space...
|
| « Last Edit: Mar 27th, 2012, 2:01am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum non existing number
« Reply #3 on: Mar 27th, 2012, 8:29am » |
Quote Modify
|
on Mar 26th, 2012, 12:53pm, towr wrote:Are the number in the array distinct?
Because if that's the case an O(n) time O(1) solution readily comes to mind. (Start by pivoting around 0 and discarding all number <= 0; Then repeatedly pick a pivot and check if the largest number in the 'small' equals the number of elements in it to see if there's one missing.) |
|
Wouldn't that be O(n log n)?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #4 on: Mar 27th, 2012, 8:44am » |
Quote Modify
|
No, because on average you can throw half the array away, you only need to seek further in one of the two parts.
It's no different in complexity then finding the kth median.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum non existing number
« Reply #5 on: Mar 27th, 2012, 9:26am » |
Quote Modify
|
But then you need more than O(1) space.
Unless you can reuse the original array, in which case I do agree.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #6 on: Mar 27th, 2012, 9:47am » |
Quote Modify
|
Quicksort also uses the space of the original array, right? So I think it should work.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #7 on: Mar 28th, 2012, 7:21pm » |
Quote Modify
|
on Mar 26th, 2012, 12:53pm, towr wrote:Are the number in the array distinct?
Because if that's the case an O(n) time O(1) solution readily comes to mind. (Start by pivoting around 0 and discarding all number <= 0; Then repeatedly pick a pivot and check if the largest number in the 'small' equals the number of elements in it to see if there's one missing.) |
|
Can you explain your solution. What is 'small' here ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #8 on: Mar 28th, 2012, 10:30pm » |
Quote Modify
|
Here's an example
We start with the array:
[3, 8, -1, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18]
We pivot around 0 so we can select the positive elements
small=[-1] large=[8, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18, 3]
discard array with elements smaller or equal to 0.
[8, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18, 3]
We have 19 elements left, so pick the next pivot to be around half, say 10.
small=[8, 3, 2, 1, 7, 5, 9, 4, 6, 10] large=[11, 15, 19, 20, 16, 14, 18, 13, 17]
The small array contains 10 elements, so every number <=10 is accounted for (because they're unique, >=1 and <=10) so we can discard the small array.
[11, 15, 19, 20, 16, 14, 18, 13, 17]
We have 9 elements left, and the minimum is 11, so let's pivot around 15.
small=[11, 15, 13, 14] large=[18, 16, 20, 17, 19]
There are 4 elements in the small array, but there should be 5 if there wasn't one missing (it should contain 11-15). So we need to search the small array further and can discard the large one.
[11, 15, 13, 14]
Pick the pivot about halfway 11 and 15, so 13.
small=[11, 13] large=[14, 15]
The small array has two elements, but should contain 11, 12 and 13 if there wasn't one missing. So again we discard the large array and continue to search the small one.
[11, 13]
At this point it's probably fastest to just see which one is missing, Rather than to repeat the divide and conquer strategy. In either case we'll find that 12 is the smallest missing element.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #9 on: Mar 28th, 2012, 10:57pm » |
Quote Modify
|
on Mar 28th, 2012, 10:30pm, towr wrote:Here's an example
We start with the array:
[3, 8, -1, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18]
We pivot around 0 so we can select the positive elements
small=[-1] large=[8, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18, 3]
discard array with elements smaller or equal to 0.
[8, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18, 3]
We have 19 elements left, so pick the next pivot to be around half, say 10.
small=[8, 3, 2, 1, 7, 5, 9, 4, 6, 10] large=[11, 15, 19, 20, 16, 14, 18, 13, 17]
The small array contains 10 elements, so every number <=10 is accounted for (because they're unique, >=1 and <=10) so we can discard the small array.
[11, 15, 19, 20, 16, 14, 18, 13, 17]
We have 9 elements left, and the minimum is 11, so let's pivot around 15.
small=[11, 15, 13, 14] large=[18, 16, 20, 17, 19]
There are 4 elements in the small array, but there should be 5 if there wasn't one missing (it should contain 11-15). So we need to search the small array further and can discard the large one.
[11, 15, 13, 14]
Pick the pivot about halfway 11 and 15, so 13.
small=[11, 13] large=[14, 15]
The small array has two elements, but should contain 11, 12 and 13 if there wasn't one missing. So again we discard the large array and continue to search the small one.
[11, 13]
At this point it's probably fastest to just see which one is missing, Rather than to repeat the divide and conquer strategy. In either case we'll find that 12 is the smallest missing element.
|
|
This solution looks O(n log n) to me.
Since the step of dividing the array is itselt O(n).
One approach that i can think of is:
1. Discard -ve elements (as you did in step 1)
2. Startting from beginning of the array, for each element x, try to place it on index [x-1] of the array. If the element present at index[x-1] is x, then skip it otherwise repeat for that element also.
3. First i such that a[i-1] != i if the answer.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #10 on: Mar 28th, 2012, 11:15pm » |
Quote Modify
|
int _tmain(int argc, _TCHAR* argv[])
{
int a[19] = {8, 17, 2, 13, 7, 5, 16, 20, 6, 15, 10, 11, 4, 19, 9, 1, 14, 18, 3};
int n = 19;
for(int i=0; i<n; i++)
{
if(a[i] > n)
continue;
if(a[i] < 0)
continue;
if(a[i] == i+1)
continue;
else
{
int loc = a[i] - 1; //ideal location for a[i]
if(a[loc] != a[i])
{
a[i] = a[loc];
a[loc] = loc+1;
i--;
}
else
continue;
}
}
for(int i=0; i<n; i++)
if(a[i] != i+1)
{
printf("%d\n",i+1);
return 0;
}
printf("%d\n",n+1);
return 0;
}
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Minimum non existing number
« Reply #11 on: Mar 29th, 2012, 5:31am » |
Quote Modify
|
on Mar 28th, 2012, 10:57pm, birbal wrote:This solution looks O(n log n) to me.
Since the step of dividing the array is itselt O(n). |
|
No, since you're discarding elements, each step is smaller than the last. On average, you will traverse n + n/2 + n/4 + n/8 + ... = 2n elements. (Although, like quicksort, it does have an O(n2) worst-case performance for pathological inputs.)
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #12 on: Mar 29th, 2012, 8:32am » |
Quote Modify
|
on Mar 29th, 2012, 5:31am, SMQ wrote:| (Although, like quicksort, it does have an O(n2) worst-case performance for pathological inputs.) |
|
Actually, I don't think it does. If you have n elements, with previous pivot p, then taking the next pivot p+n/2 guarantees that there are at most n/2 elements the next step, because either the "small" array contains n/2 elements and is discarded -- leaving the n/2 in the "large" array; or it contains less than n/2 elements and must thus miss at least one number.
Besides, isn't quicksort guaranteed O(n log n) when you choose the pivot with median of medians?
|
| « Last Edit: Mar 29th, 2012, 8:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #13 on: Mar 29th, 2012, 12:13pm » |
Quote Modify
|
on Mar 29th, 2012, 8:32am, towr wrote:
Actually, I don't think it does. If you have n elements, with previous pivot p, then taking the next pivot p+n/2 guarantees that there are at most n/2 elements the next step, because either the "small" array contains n/2 elements and is discarded -- leaving the n/2 in the "large" array; or it contains less than n/2 elements and must thus miss at least one number.
Besides, isn't quicksort guaranteed O(n log n) when you choose the pivot with median of medians? |
|
I see....This clarifies a lot...Its indeed worst case O(n)
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #14 on: Mar 29th, 2012, 1:25pm » |
Quote Modify
|
And an even simpler approach, if you don't mind destroying the array -- and which will work even if you have multiple occurrences -- is to swap every element into its proper place (i.e. element i to arr[i-1]). Throw away doubles and elements out of bound, replacing them with a 0. Then when you reach the end, search for the first 0.
Something like
for (i=0; i < n i++)
{
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
continue;
}
while (a[t] > 0)
{
a[i] = a[t];
a[t] = t;
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
break;
}
}
}
for (i=0; i < n i++)
if (a[i] ==0)
return i+1;
(Probably not entirely correct, it's late and I have a headache.)
|
| « Last Edit: Mar 29th, 2012, 1:31pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #15 on: Mar 30th, 2012, 5:36am » |
Quote Modify
|
on Mar 29th, 2012, 1:25pm, towr wrote:And an even simpler approach, if you don't mind destroying the array -- and which will work even if you have multiple occurrences -- is to swap every element into its proper place (i.e. element i to arr[i-1]). Throw away doubles and elements out of bound, replacing them with a 0. Then when you reach the end, search for the first 0.
Something like
for (i=0; i < n i++)
{
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
continue;
}
while (a[t] > 0)
{
a[i] = a[t];
a[t] = t;
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
break;
}
}
}
for (i=0; i < n i++)
if (a[i] ==0)
return i+1;
(Probably not entirely correct, it's late and I have a headache.) |
|
Looks similar to the approach that i have given in one of my posts above 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #16 on: Mar 30th, 2012, 8:55am » |
Quote Modify
|
You're right. And yours even a bit nicer too, cleverly avoiding a nested loop by simply decrementing the counter. Although I don't think yours handles doubles (seems like that would cause a loop); but that can easily be fixed.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nova2358
Newbie
Posts: 3
|
|
Re: Minimum non existing number
« Reply #17 on: Apr 3rd, 2012, 9:25am » |
Quote Modify
|
on Mar 26th, 2012, 12:53pm, towr wrote:Are the number in the array distinct?
Because if that's the case an O(n) time O(1) solution readily comes to mind. (Start by pivoting around 0 and discarding all number <= 0; Then repeatedly pick a pivot and check if the largest number in the 'small' equals the number of elements in it to see if there's one missing.) |
|
Your solution is good. Originally I thought it was impossible to find an O(n) solution. The idea of selecting a pivot can reduce the running time from O(n log n) to O(n). Because we can reduce the running time from T(n) = 2T(n/2) + O(n) to T(n) = T(n/2) + O(n).
I have been interviewed with 2 questions like this. Quick select can provide an average O(n) solution and the median of median algorithm can guarantee a O(n) solution in worst case.
|
|
IP Logged |
|
|
|
jianqiang
Newbie
Posts: 4
|
|
Re: Minimum non existing number
« Reply #18 on: Apr 7th, 2012, 2:53am » |
Quote Modify
|
first scan the vector , and find the minimal number, let it be Min. n is the size the vector. Then visit each element of the vector again.
for (i = 0; i < n; i++)
{
t = a[i];
if (t < Min)
{
t += Min;
}
if (t <= 0 || t > n)
{
continue; //a[i] can not be the minimal non existing number.
}
a[t-1] = 2Min-a[t-1];
}
then traverse the vector to find the minimal non-existing positive integer and restore vector
non_exist = -1;
for (i = 0;i < n ; i++)
{
if (a[i] < Min)
{
a[i] = 2Min-a[i];
}
else if (non_exist < 0)
{
non_exist = i+1;
}
}
if (non_exist < 0)
{
non_exist = n + 1;
}
|
| « Last Edit: Apr 7th, 2012, 8:58am by jianqiang » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #19 on: Apr 8th, 2012, 2:54am » |
Quote Modify
|
on Mar 29th, 2012, 1:25pm, towr wrote:And an even simpler approach, if you don't mind destroying the array -- and which will work even if you have multiple occurrences -- is to swap every element into its proper place (i.e. element i to arr[i-1]). Throw away doubles and elements out of bound, replacing them with a 0. Then when you reach the end, search for the first 0.
Something like
for (i=0; i < n i++)
{
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
continue;
}
while (a[t] > 0)
{
a[i] = a[t];
a[t] = t;
t = a[i];
if (t <=0 || t >=n)
{
a[i]=0;
break;
}
}
}
for (i=0; i < n i++)
if (a[i] ==0)
return i+1;
(Probably not entirely correct, it's late and I have a headache.) |
|
How does yours handle duplicate. I guess both the programs will fail in case of dublicates. Yours will go to an infinite loop and mine will terminate without giving valid result.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum non existing number
« Reply #20 on: Apr 8th, 2012, 6:36am » |
Quote Modify
|
If you read the description (which isn't faithfully implemented in the code below it -- hence the disclaimers), you can read that I'd just replace duplicates by 0. Just an extra check you need to do before swapping.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Minimum non existing number
« Reply #21 on: Apr 8th, 2012, 7:24am » |
Quote Modify
|
on Apr 8th, 2012, 6:36am, towr wrote:| If you read the description (which isn't faithfully implemented in the code below it -- hence the disclaimers), you can read that I'd just replace duplicates by 0. Just an extra check you need to do before swapping. |
|
Yeah, read it now...
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print