Author |
Topic: To find lowest missing whole number (Read 1357 times) |
|
coderyogi
Newbie
Posts: 29
|
 |
To find lowest missing whole number
« on: Apr 3rd, 2010, 12:59am » |
 Quote  Modify
|
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  , is the time complexity in terms of array size linear or quadratic?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: To find lowest missing whole number
« Reply #1 on: Apr 3rd, 2010, 3:22am » |
Quote Modify
|
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).
|
| « Last Edit: Apr 3rd, 2010, 3:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: To find lowest missing whole number
« Reply #2 on: Apr 3rd, 2010, 8:27am » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
coderyogi
Newbie
Posts: 29
|
|
Re: To find lowest missing whole number
« Reply #3 on: Apr 5th, 2010, 9:22am » |
Quote Modify
|
@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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: To find lowest missing whole number
« Reply #4 on: Apr 5th, 2010, 11:54am » |
Quote Modify
|
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? 
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: To find lowest missing whole number
« Reply #5 on: Apr 5th, 2010, 12:04pm » |
Quote Modify
|
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). 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: To find lowest missing whole number
« Reply #6 on: Apr 5th, 2010, 1:30pm » |
Quote Modify
|
on Apr 5th, 2010, 12:04pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: To find lowest missing whole number
« Reply #7 on: Apr 5th, 2010, 10:08pm » |
Quote Modify
|
on Apr 5th, 2010, 9:22am, 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.
|
|
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: To find lowest missing whole number
« Reply #8 on: Apr 5th, 2010, 10:11pm » |
Quote Modify
|
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??
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: To find lowest missing whole number
« Reply #9 on: Apr 6th, 2010, 10:37am » |
Quote Modify
|
partial sorting may not work if the input array contains duplicate elements.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: To find lowest missing whole number
« Reply #10 on: Apr 6th, 2010, 12:12pm » |
Quote Modify
|
on Apr 6th, 2010, 10:37am, sateesp wrote:| partial sorting may not work if the input array contains duplicate elements. |
|
Yeah, I said that already when I proposed it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
coderyogi
Newbie
Posts: 29
|
|
Re: To find lowest missing whole number
« Reply #11 on: Apr 10th, 2010, 10:27pm » |
Quote Modify
|
on Apr 5th, 2010, 10:11pm, kaka189 wrote: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?? |
|
Thanks kaka189, pretty good solution!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print