time required to fins the unknowm integer

Question

as we already know the range,so can we use counting sort??and complexity of counting sort is O(n+k)

what other method is there to know the missing number??

Comments

..........................

Answer 1

• $XOR$ all the array elements like a[0] XOR a[1] XOR a[2] XOR a[3].............. XOR a[n].

Say this as A.

• $XOR$ all the natural numbers like 0 XOR 1 XOR 2 XOR 3 XOR ................... XOR N.

Say this as B.

The missing number will be A XOR B.

---

• Another method is to use the sum of $1$st $N$ natural numbers and substract all the elements from the sum .

Comments

@akriti search on geeksforgeeks for xor method

---

hashing can also be used since we know the range

---

xor is best here

Answer 2

We know that integers are between 0 to n.

 

Create an auxilary array B of size (n+1) with index 0 to n

Now, go on scanning the integers one by one and then place the integer into its original place in array B. If the number doesnt map to any place, you got the unknown integer.

So, O(n)

Comments

@sushant,this is counting sort only..right?

---

why did u scrap your answer???

---

Got it back