You are given an integer array arr, write a program to return the smallest missing positive integer.

Problem Note

• The array is unsorted.
• You need to return the smallest natural number that is not in the list
• You are expected to solve this in O(n) time using O(1) extra space.

Example 1

Input: arr[] = [5,1,7,3,9,2,4]
Output: 6
Explanation: In the above example, 6 and 8 are missing in the input array. But 6 is the smallest missing number. Hence, the output is 6.

Example 2

Input: arr[] = [5,8,3,6,2]
Output: 1
Explanation: In the above example, 1, 4, and 7 are missing in the input array. But 1 is the smallest missing number. Hence, the output is 1.

Example 3

Input: arr[] = [1,4,3,2]
Output: 5
Explanation: In the above example, no natural number is missing in between the input elements. So, we'll take the number just after the largest input element. Hence, the output is 5.