wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Minimum non existing number
        
(Message started by: birbal on Mar 26th, 2012, 12:06pm)
Title: Minimum non existing number
Post by birbal on Mar 26th, 2012, 12:06pm
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?
Title: Re: Minimum non existing number
Post by towr on Mar 26th, 2012, 12:53pm
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.)
Title: Re: Minimum non existing number
Post by Grimbal on Mar 27th, 2012, 2:00am
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...
Title: Re: Minimum non existing number
Post by Grimbal on Mar 27th, 2012, 8:29am

on 03/26/12 at 12:53:30, 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)?
Title: Re: Minimum non existing number
Post by towr on Mar 27th, 2012, 8:44am
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.
Title: Re: Minimum non existing number
Post by Grimbal on Mar 27th, 2012, 9:26am
But then you need more than O(1) space.

Unless you can reuse the original array, in which case I do agree.
Title: Re: Minimum non existing number
Post by towr on Mar 27th, 2012, 9:47am
Quicksort also uses the space of the original array, right? So I think it should work.
Title: Re: Minimum non existing number
Post by birbal on Mar 28th, 2012, 7:21pm

on 03/26/12 at 12:53:30, 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 ?
Title: Re: Minimum non existing number
Post by towr on Mar 28th, 2012, 10:30pm
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.
Title: Re: Minimum non existing number
Post by birbal on Mar 28th, 2012, 10:57pm

on 03/28/12 at 22:30:31, 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.
Title: Re: Minimum non existing number
Post by birbal on Mar 28th, 2012, 11:15pm
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;
}
Title: Re: Minimum non existing number
Post by SMQ on Mar 29th, 2012, 5:31am

on 03/28/12 at 22:57:31, 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
Title: Re: Minimum non existing number
Post by towr on Mar 29th, 2012, 8:32am

on 03/29/12 at 05:31:59, 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?
Title: Re: Minimum non existing number
Post by birbal on Mar 29th, 2012, 12:13pm

on 03/29/12 at 08:32:37, 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)
Title: Re: Minimum non existing number
Post by towr on Mar 29th, 2012, 1:25pm
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.)
Title: Re: Minimum non existing number
Post by birbal on Mar 30th, 2012, 5:36am

on 03/29/12 at 13:25:50, 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  :)
Title: Re: Minimum non existing number
Post by towr on Mar 30th, 2012, 8:55am
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.
Title: Re: Minimum non existing number
Post by nova2358 on Apr 3rd, 2012, 9:25am

on 03/26/12 at 12:53:30, 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.  
Title: Re: Minimum non existing number
Post by jianqiang on Apr 7th, 2012, 2:53am
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;
}
Title: Re: Minimum non existing number
Post by birbal on Apr 8th, 2012, 2:54am

on 03/29/12 at 13:25:50, 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.
Title: Re: Minimum non existing number
Post by towr on Apr 8th, 2012, 6:36am
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.
Title: Re: Minimum non existing number
Post by birbal on Apr 8th, 2012, 7:24am

on 04/08/12 at 06:36:25, 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...:)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board