Answer to Question #174124 in Python for CHANDRASENA REDDY CHADA

Question

Smallest Missing Number

Given a list of numbers, write a program to print the smallest positive integer missing in the given numbers.Input

The input will be a single line containing numbers separated by space.Output

The output should be a single line containing the smallest missing number from given numbers.Explanation

For example, if the input numbers are 3, 1, 2, 5, 3, 7, 7.

The number 1, 2, 3 are present. But the number 4 is not. So 4 is the smallest positive integers that is missing from the given numbers.

Sample Input 1

3 1 2 5 3 7 7

Sample Output 1

4

Sample Input 2

5 5 2 3 1 8 8 4

Sample Output 2

6

Answer 1

def segregate(arr, size):
    j = 0
    for i in range(size):
        if (arr[i] <= 0):
            arr[i], arr[j] = arr[j], arr[i]
            j += 1 # increment count of non-positive integers
    return j
 
 
''' Find the smallest positive missing number
in an array that contains all positive integers '''
def findMissingPositive(arr, size):
     
    # Mark arr[i] as visited by
    # making arr[arr[i] - 1] negative.
    # Note that 1 is subtracted
    # because index start
    # from 0 and positive numbers start from 1
    for i in range(size):
        if (abs(arr[i]) - 1 < size and arr[abs(arr[i]) - 1] > 0):
            arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]
             
    # Return the first index value at which is positive
    for i in range(size):
        if (arr[i] > 0):
             
            # 1 is added because indexes start from 0
            return i + 1
    return size + 1
 
''' Find the smallest positive missing
number in an array that contains
both positive and negative integers '''
def findMissing(arr, size):
     
    # First separate positive and negative numbers
    shift = segregate(arr, size)
     
    # Shift the array and call findMissingPositive for
    # positive part
    return findMissingPositive(arr[shift:], size - shift)
     
# Driver code
arr = [ 0, 10, 2, -10, -20 ]
arr_size = len(arr)
missing = findMissing(arr, arr_size)
print("The smallest positive missing number is ", missing)