CSES: Missing Number Solution

Problem Statement

Problem Statement Link: CSES 1083: Missing Number Solution Link

You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.

Input

The first input line contains an integer n.
The second line contains n-1 numbers. Each number is distinct and between 1 and n (inclusive).

Output

Print the missing number.

Constraints

2 <= n <= 2*10^5

Example
Input:
5
2 3 1 5

Output:
4

Solution

import sys

def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())

def find_missing_number(n, a):
    # Initialize the result variable
    ans = 0
    
    # XOR all the given numbers in the list 'a'
    for i in a:
        ans = ans ^ i
    
    # XOR the numbers from 1 to n
    for i in range(1, n+1):
        ans = ans ^ i
    
    # The remaining value in 'ans' is the missing number
    return ans

if __name__ == "__main__":
    # Read the range 'n' and the list of numbers 'a'
    n = int(input())
    a = linput()
    
    # Find and print the missing number
    result = find_missing_number(n, a)
    print(result)

Explanation

Certainly! Let’s break down the logic behind the solution and why it works.

Problem Statement:
You are given all numbers between 1, 2, …, n except one. Your task is to find the missing number.

Solution Explanation:

1. XOR Operation:
   The solution relies on the properties of the XOR (exclusive OR) operation. XORing a number with itself results in 0, and XORing a number with 0 gives the number itself. Additionally, XOR is commutative and associative.
2. XORing the Given Numbers:
   The loop for i in a: XORs all the given numbers in the list a. Since each number appears twice (except the missing one), XORing all the numbers will cancel out duplicates, leaving only the missing number.

3. XORing Numbers from 1 to n:
   The second loop for i in range(1, n+1): XORs all the numbers from 1 to n. This includes the missing number. If we XOR the result obtained from step 2 with the XOR of numbers from 1 to n, the duplicates (numbers from 1 to n) will cancel out, leaving only the missing number.

4. Final Result:
   The final result stored in the variable ans after both XOR operations is the missing number. This is because XORing the duplicates cancels them out, leaving only the missing number.

In summary, the solution takes advantage of the XOR operation to efficiently find the missing number in a given range. The time complexity of the solution is O(n), where n is the size of the input list.

You can find more blogs here.