wu :: forums - Print Page


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

        riddles >> cs >> To find lowest missing whole number
        
(Message started by: coderyogi on Apr 3^rd, 2010, 12:59am)

Title: To find lowest missing whole number
Post by coderyogi on Apr 3^rd, 2010, 12:59am

Question: An array contains only whole numbers. To find the lowest missing whole number.

Proposed solution:
int is_it_correct(int *arr, int size)
{
for (ctr1 = 0; ctr1 < pow(2, 8 * sizeof(int)); ctr1++) {
for (ctr2 = 0; ctr2 < size; ctr2++) {
if (arr[ctr2] ^ ctr1);
else
break;
}
if (ctr2 == size)
return ctr1;
}
return -1; //all numbers present
}

I hope this works fine. If my hope is correct :P, is the time complexity in terms of array size linear or quadratic?

Title: Re: To find lowest missing whole number
Post by towr on Apr 3^rd, 2010, 3:22am

It would be quadratic.

You can do it faster by sorting; which would give O(n log n)
And if there aren't any doubles, you can do partial sorting, for O(n).
Or you could use a hash-table, or even just a bitmap (if you have a 32-bit integer, 540MB memory is enough).

Title: Re: To find lowest missing whole number
Post by kaka189 on Apr 3^rd, 2010, 8:27am

since the numbers are positive. Traverse the array, if a[i] = k , make kth number negative (take i as -i if -ve and ignore if k >= n). iterate again to find the first +ve number as result and make the all numbers positive if we dont want the array state to be changed. Looks like inplace and O(n) time algo if the array is not read only :)

Title: Re: To find lowest missing whole number
Post by coderyogi on Apr 5^th, 2010, 9:22am

@towr, thanks.
The problem i'm facing with hashing is the compiler complaining that array size is too large as the array has to have an index till the max number in a machine, i.e. pow(2, 8 * sizeof(int)).

@kaka189, i couldn't understand your solution.

Title: Re: To find lowest missing whole number
Post by blackJack on Apr 5^th, 2010, 11:54am

Quote:

Or you could use a hash-table, or even just a bitmap

How can we use a hash-table to search the missing number? :-[

Title: Re: To find lowest missing whole number
Post by blackJack on Apr 5^th, 2010, 12:04pm

Ahh .... I think hash-tables can be used first for storing all the array elements and then we will search from start if some value is not present in hashtable. ::)

And how partial sorting can be used in O(n). :-/

Title: Re: To find lowest missing whole number
Post by towr on Apr 5^th, 2010, 1:30pm

on 04/05/10 at 12:04:31, blackJack wrote:

And how partial sorting can be used in O(n). :-/

Pick a pivot K, partition the array into ones greater and smaller than K, if there are less than K elements smaller or equal to K, then there is an element missing from that subset. Otherwise, there is either a number missing from the other subset, or there isn't any number missing.

Title: Re: To find lowest missing whole number
Post by kaka189 on Apr 5^th, 2010, 10:08pm

on 04/05/10 at 09:22:41, coderyogi wrote:

@kaka189, i couldn't understand your solution.

ex: take an array of size 10, lowest missing number is 6.
ret = -1;
for ( i = 0; i <10 ; i++)
{
if(a[i] < 10)
{
if(a[i] < 0 ) a[ -a[i] ] * = -1;
else a[ a[i] ] * = -1;
}
}

for(i=0;i< 10;i++)
{
if(a[i] > 0 && ret != -1) ret = i;
else a[i]*=-1;
}

8, 5, 11, 16 , 2, 4, 9, 3, 0, 1
Then after first for loop, array will be
-8,-2,-11,-16,-2,-4,9,3, 0 ,1

so first +ve number is in 6th position. So answer is 6 .
Please let me know if something is wrong with it.

Title: Re: To find lowest missing whole number
Post by kaka189 on Apr 5^th, 2010, 10:11pm

hey. just realized that having a zero will cause a problem as we cant negate it. So instead of making just negative, add 1 and make negative. a[a[i] = (a[a[i] + 1)*-1. and in second for loop revert it back.

Its O(n) time, O(1) space solution. anything wrong now??

Title: Re: To find lowest missing whole number
Post by sateesp on Apr 6^th, 2010, 10:37am

partial sorting may not work if the input array contains duplicate elements.

Title: Re: To find lowest missing whole number
Post by towr on Apr 6^th, 2010, 12:12pm

on 04/06/10 at 10:37:26, sateesp wrote:

partial sorting may not work if the input array contains duplicate elements.

Yeah, I said that already when I proposed it.

Title: Re: To find lowest missing whole number
Post by coderyogi on Apr 10^th, 2010, 10:27pm

on 04/05/10 at 22:11:44, kaka189 wrote:

Thanks kaka189, pretty good solution!