Original link:http://www.careercup.com/question?id=12708671
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Eg:
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1
Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.
Eg:
Input = {2, 3, 7, 6, 8, -1, -10, 15}
Output = 1
Input = { 2, 3, -7, 6, 8, 1, -10, 15 }
Output = 4
Solution:
1.) Partition the array into the values smaller than zero and +ve integers using the Quicksort partition method. This can be done in O(n) time and in the same array.
2.) Now you the index of element '0' or first +ve number, say this is idxZ.
3.) Traverse starting from idxZ and set the sign bit of the value at position (idxZ + A[idxZ]) to 1. You do this only in case the value of position lies in the bounds of array.
4.) Now starting at 'idxZ' find the first position where the sign bit is UNSET. This gives you the number you are looking for.
