In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same as below:
#include<bits/stdc++.h>
using namespace std;
int main(){
int arr[]={1,-1,-5,-3,3,4,2,8};
int size= sizeof(arr)/sizeof(arr[0]);
sort(arr, arr+size);
int min=1;
for(int i=0; i<size; i++){
if(arr[i]>min) break;
if(arr[i]==min) min=min+1;
}
cout<<min;
return 0;
}
Here, I am first sorting the array, and then traversing the array once. Before traversing the array, I have initialized a variable named "min" as 1. Now, while traversing the array, when we get an integer that is equal to min, we simply increment the value of min. This ensures that the min variable hold the latest least positive integer that has not occurred yet. Can you think of any better approach? Thanks in advance.
Answer: LCM of 6, 8, and 10 is 120. Explanation: The LCM of three non-zero integers, a(6), b(8), and c(10), is the smallest positive integer m(120) that is divisible by a(6), b(8), and c(10) without any remainder.
Solution steps We create a hash table H of size n. Now we run a loop from i = 0 to n - 1 and insert all elements in the hash table H. Now we another loop from i = 1 to n + 1 to search all the possible positive numbers from 1 to n + 1 in the hash table H. If any positive integer i is not present in H, we return i.
Assuming the array can be modified,
We divide the array into 2 parts such that the first part consists of only positive numbers. Say we have the starting index as 0
and the ending index as end
(exclusive).
We traverse the array from index 0
to end
. We take the absolute value of the element at that index - say the value is x
.
x > end
we do nothing.x-1
negative. (Clarification: We do not toggle the sign. If the value is positive, it becomes negative. If it is negative, it remains negative. In pseudo code, this would be something like if (arr[x-1] > 0) arr[x-1] = -arr[x-1]
and not arr[x-1] = -arr[x-1]
.)Finally, we traverse the array once more from index 0
to end
. In case we encounter a positive element at some index, we output index + 1
. This is the answer. However, if we do not encounter any positive element, it means that integers 1
to end
occur in the array. We output end + 1
.
It can also be the case that all the numbers are non-positive making end = 0
. The output end + 1 = 1
remains correct.
All the steps can be done in O(n)
time and using O(1)
space.
Example:
Initial Array: 1 -1 -5 -3 3 4 2 8
Step 1 partition: 1 8 2 4 3 | -3 -5 -1, end = 5
In step 2 we change the signs of the positive numbers to keep track of which integers have already occurred. For example, here array[2] = -2 < 0
, it suggests that 2 + 1 = 3
has already occurred in the array. Basically, we change the value of the element having index i
to negative if i+1
is in the array.
Step 2 Array changes to: -1 -8 -2 -4 3 | -3 -5 -1
In step 3, if some value array[index]
is positive, it means that we did not find any integer of value index + 1
in step 2.
Step 3: Traversing from index 0 to end, we find array[4] = 3 > 0
The answer is 4 + 1 = 5
This is actually a LeetCode problem that asks for O(n)
time and O(1)
space, so sorting the input or converting it to a set won't work.
Here's a Python 3 implementation of pmcarpan's answer that runs in O(n)
time and uses O(1)
space.
def missing_int(nums: MutableSequence[int]) -> int:
# If empty array or doesn't have 1, return 1
if not next((x for x in nums if x == 1), 0):
return 1
lo: int = 0
hi: int = len(nums) - 1
i: int = 0
pivot: int = 1
while i <= hi:
if nums[i] < pivot:
swap(nums, i, hi)
hi -= 1
elif nums[i] > pivot:
swap(nums, i, lo)
i += 1
lo += 1
else:
i += 1
x = 0
while x <= hi: # hi is the index of the last positive number
y: int = abs(nums[x])
if 0 < y <= hi + 1 and nums[y - 1] > 0: # Don't flip sign if already negative
nums[y - 1] *= -1
x += 1
return next((i for i, v in enumerate(nums[:hi + 1]) if v >= 0), x) + 1
Tests:
def test_missing_int(self):
assert func.missing_int([1, 2, 1, 0]) == 3
assert func.missing_int([3, 4, -1, 1]) == 2
assert func.missing_int([7, 8, 9, 11, 12]) == 1
assert func.missing_int([1]) == 2
assert func.missing_int([]) == 1
assert func.missing_int([0]) == 1
assert func.missing_int([2, 1]) == 3
assert func.missing_int([-1, -2, -3]) == 1
assert func.missing_int([1, 1]) == 2
assert func.missing_int([1000, -1]) == 1
assert func.missing_int([-10, -3, -100, -1000, -239, 1]) == 2
assert func.missing_int([1, 1]) == 2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With