Created With

You are given an array A of n-1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number.

missing.py1linkn = 52linka = [3, 5, 1, 4]3link4linkoriginal = list(range(1, n+1)  # [1, 2, 3, 4, 5]5linkmissing = 06linkfor v in a+orig:  # [3, 5, 1, 4, 1, 2, 3, 4, 5]7link  missing ^= v8link9linkprint(missing)
• First we generate a list of integers containing ALL of the numbers from 1 to n.
• We go through each value of the combined list of a and original.
• We now remove the duplicates, and the remaining number is the one that is missing. This is achieved by using the XOR operator.
• Why is that?chevron_right
1linkXOR is commutative2link  a ^ b ^ c == c ^ b ^ a3link4linkWe can use XOR to remove duplicates5link  a ^ b ^ c ^ b ^ a6link  a ^ a ^ b ^ b ^ c7link  0 ^ 0 ^ c8link  c9link10linkUsing our example above11link  3 ^ 5 ^ 1 ^ 4 ^ 1 ^ 2 ^ 3 ^ 4 ^ 512link  1 ^ 1 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 5 ^ 213link  0 ^ 0 ^ 0 ^ 0 ^ 214link  2

15-Feb-2021

Find The Missing Number

Home

Awesome Stuff

Project Eulerchevron_right
Essayschevron_right
Blogschevron_right