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:
- 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. - XORing the Given Numbers:
The loopfor i in a:
XORs all the given numbers in the lista
. Since each number appears twice (except the missing one), XORing all the numbers will cancel out duplicates, leaving only the missing number.
- XORing Numbers from 1 to n:
The second loopfor 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.
- Final Result:
The final result stored in the variableans
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.