Python Program to Find Missing Integer in an Array.

Problem Statement.

Given an integer array of size n-1 and the array containing distinct numbers in a range of [1, n]. The task is to write a Python program to find the missing number from the array.

Example:

Input: arr = [1, 2, 3, 4, 6]
Output: Missing Number is 5

Input: arr = [3, 1, 2, 5, 7, 6]
Output: Missing Number is 4

There are multiple approaches to finding the missing number in an array and here we are going to discuss three of them.

Using Set.
Using XOR.
Using Summation.

Python Program to Find Missing Number Using Set.

In this approach, we are using a set data structure to efficiently identify the missing number in a given sequence or array.

Algorithm:

Step 1: Convert the given sequence or array into a set for efficient lookup operations.

Step 2: Create a set containing all the numbers in the expected range or sequence.

Step 3: Subtract the set of given numbers from the set of expected numbers.

Step 4: The remaining elements in the expected set would be the missing number.

Python Code:

def find_missing_integer(arr):
    n = len(arr) + 1  # Including the missing integer

    full_set = set(range(1, n + 1))
    arr_set = set(arr)

    missing_integer = full_set - arr_set

    return missing_integer.pop()

arr = [1, 2, 3, 4, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 5

Time Complexity: The time complexity of the above approach is O(n) because the construction of the set takes O(n) time and the subtraction of one set with another also takes O(n) time.

Space Complexity: The space complexity is O(n) as it requires additional space to store the sets of expected and given numbers.

Python Program to Find Missing Number of Array Using XOR.

The XOR approach utilizes the properties of the XOR operation to find the missing number in an array. XORing any number with itself results in 0 so all identical elements cancel out each other.

Algorithm:

Step 1: Iterate through the given array and XOR all the elements with each other.

Step 2: XOR all the numbers from 1 to n to obtain a cumulative XOR value.

Step 3: XOR the cumulative XOR value from Step 1 with the XOR value from Step 2.

Step 4: The result will be the missing number in the array.

Python Code:

# Python code implementation to find missing number
def find_missing_integer(arr):
    n = len(arr) + 1  
    xor_full = 0
    xor_arr = 0

    # XOR of all numbers from 1 to n
    for i in range(1, n + 1):
        xor_full ^= i

    # XOR of all numbers in the array
    for num in arr:
        xor_arr ^= num

    missing_integer = xor_full ^ xor_arr
    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

Time Complexity: O(n) because we have to iterate through the array to perform XOR operations.

Space Complexity: O(1) because we have used a constant amount of extra space for variables.

Python Program to Find Missing Number of Array Using Summation.

In this approach, we are using math formulas to find the sum of the first n natural numbers. Then we subtract the sum of the array with the sum of the natural number and it will return us the missing number.

Algorithm:

Step 1: Iterate through the given array and calculate the sum of all the elements.

Step 2: Determine the expected sum of all the numbers in the sequence from 1 to n. This can be calculated using the formula: (n * (n+1))/2.

Step 3: Subtract the sum of the given numbers from the expected sum. The result will be the missing number.

Python Code:

# Python code to find missing number using math
def find_missing_integer(arr):
    n = len(arr) + 1  

    expected_sum = n * (n + 1) // 2

    actual_sum = sum(arr)
    missing_integer = expected_sum - actual_sum

    return missing_integer

arr = [3, 1, 2, 5, 7, 6]
print("Missing Number is",find_missing_integer(arr))

Output:

Missing Number is 4

Time Complexity: O(n) because we have to iterate through the array to calculate the sum of array elements.

Space Complexity: O(1) as no extra space is required in this approach to find the missing number.

Python Program to Find Missing Integer in an Array.

Problem Statement.

Python Program to Find Missing Number Using Set.

Python Program to Find Missing Number of Array Using XOR.

Python Program to Find Missing Number of Array Using Summation.

No comments:

Post a Comment