Given a list of numbers from 1 to n find the missing number in Python

 To find the missing number in a list containing numbers from 1 to 

$n$ with exactly one number missing, you can use several approaches. Below are a few efficient methods to solve this problem in Python:

Method 1: Sum Formula

The sum of the first $n$ natural numbers can be calculated using the formula:

$\text{Sum}_n = \frac{n \times (n + 1)}{2}$

If one number is missing, the difference between this sum and the sum of the numbers present in the list will give you the missing number.

Here's how you can implement this:

def find_missing_number(nums, n):

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

    actual_sum = sum(nums)

    return total_sum - actual_sum

# Example usage:

nums = [1, 2, 4, 5, 6]

n = 6

print(find_missing_number(nums, n))  # Output: 3

Method 2: XOR Operation

Another efficient approach is to use XOR. The key idea here is that XORing a number with itself results in 0, and XORing a number with 0 results in the number itself. This property can be utilized to find the missing number by XORing all numbers from 1 to $n$ with the numbers present in the list.

Here’s how you can do it:

def find_missing_number(nums, n):

    xor_all = 0

    xor_nums = 0

    

    for i in range(1, n + 1):

        xor_all ^= i

    

    for num in nums:

        xor_nums ^= num

    

    return xor_all ^ xor_nums

# Example usage:

nums = [1, 2, 4, 5, 6]

n = 6

print(find_missing_number(nums, n))  # Output: 3

Method 3: Using Set Operations

You can also use set operations to find the missing number by comparing the expected set of numbers with the actual set of numbers in the list.

def find_missing_number(nums, n):

    expected_set = set(range(1, n + 1))

    actual_set = set(nums)

    missing_number = expected_set - actual_set

    return missing_number.pop()  # Extract the single element from the set

# Example usage:

nums = [1, 2, 4, 5, 6]

n = 6

print(find_missing_number(nums, n))  # Output: 3

Choosing the Best Method

• Sum Formula: Simple and efficient, O(n) time complexity and O(1) space complexity.
• XOR Operation: Also very efficient, O(n) time complexity and O(1) space complexity.
• Set Operations: May be less efficient in terms of space, O(n) time complexity and O(n) space complexity.

Each method has its own advantages, so you can choose based on your specific needs or constraints.