Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding the number missing in the sequence [duplicate]

Tags:

algorithm

xor

I have been given a list of n integers and these integers are in the range of 1 to n. There are no duplicates in list.But one of the integers is missing in the list.I have to find the missing integer.

Example: If n=8
I/P    [7,2,6,5,3,1,8]
O/P    4

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
       total = n*(n+1)/2
And then Subtract all the numbers from sum.

But the above method will fail if the sum of the numbers goes beyond maximum allowed integer.

So i searched for a second solution and i found a method as follows:

 1) XOR all the elements present in arr[], let the result of XOR be R1.
 2) XOR all numbers from 1 to n, let XOR be R2.
 3) XOR of R1 and R2 gives the missing number.

How is this method working?..How is the XOR of R1 and R2 finds the missing integer in the above case?

like image 791
poorvank Avatar asked Aug 20 '13 12:08

poorvank


People also ask

How do you find the missing number in a sequence?

Step 1: Find the common difference of each pair of consecutive terms in the sequence by subtracting each term from the term that comes directly after it. Step 2: Add the common difference to the number prior to the first missing number in the sequence. Step 3: Repeat Step 2 for any other missing numbers.

How do you check out the missing number in a sorted duplicate array?

You can easily find out this by using the binary search algorithm in O(logN) time. Our solution implements this logic to find the missing integer in a sorted array in Java. You can use this solution to find the missing number in an array of numbers 1-1000 or 1 -100.

How do you find multiple missing numbers in an integer array with duplicates?

To find the multiple missing elements run a loop inside it and see if the diff is less than arr[i] – i then print the missing element i.e., i + diff. Now increment the diff as the difference is increased now. Repeat from step 2 until all the missing numbers are not found.

How do you find a number in an array which is repeated?

Duplicate elements can be found using two loops. The outer loop will iterate through the array from 0 to length of the array. The outer loop will select an element. The inner loop will be used to compare the selected element with the rest of the elements of the array.


2 Answers

To answer your question , you just have to remember that

A XOR B = C => C XOR A = B

and it immediately follows that

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR ( PATIAL SUM) = (MISSING ELEMNT)

To prove the first property, just write down the XOR truth table:

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Truth table in short : if both the bits are same, result of XOR is false, true otherwise.

On an unrelated note, this property of XOR makes it a nice candidate for simple ( but not trivial ) forms of encryption.

like image 153
Save Avatar answered Nov 09 '22 23:11

Save


First of all, you can make your original method work even in the presence of integer overflow (as long as n fits in an int).

As to the XOR method, observe that R1 xor M == R2 (where M is the missing number). From this it follows that R1 xor M xor R2 == 0 and therefore M == R1 xor R2.

like image 41
NPE Avatar answered Nov 10 '22 01:11

NPE