Question

given an array of size n with numbers b/n 1 nd n....so device an algo to find the duplicates and missing numbers....

Answer 1

i think it's like this......sort the array using merge sort nd use a compare the number with the respective index,........just wondering if there is a faster method

Answer 2

Could you rephrase? because i am not sure i understand you

Answer 3

Rephrasing (assuming I understand the question):

given an array of a particular size n that contains numbers between one and n, create an algorithm to find all duplicate and missing numbers.

For example, if the array was of size 10 and contained the following: [1,2,2,3,4,7,7,7,8,9] the algorithm should return the dupilcated numbers (2 and 7 in this case) and the missing numbers (5, 6 and 10). Note that the question does not specify that the given array be sorted, as in my example, hence the submitter's initial thought to sort the array first.

Answer 4

that's pretty easy, did you solve it @A.Avinash_Goutham ?

Answer 5

@annas You can just sort them and then perform an O(N) procedure that solves the problem, otherwise you can make an O(N^2) algorithm that solves the problem without sorting.

Answer 6

@A.Avinash_Goutham you can solve it by only iterating through the array in O(N), there's no need for sorting at all.

Answer 7

how to solve it by iterating?

Answer 8

u just used sort......
i thot that by using merge sort it wud be like o(n) + o(nlogn.)....
i was wondering if ther's a faster method

Answer 9

@A.Avinash_Goutham there is an O(N) one.Try to think of it and if you don't manage to solve it i 'll help you.Hint: you can use an array to store your results, which is a dp technique, but don't think of the problem as dp.

Answer 10

dp?

Answer 11

It's not dp.It's more like an ad-hoc problem, but if you want the optimal solution you have to store data somewhere,which is mainly a dp technique.

Answer 12

wat's dp?

Answer 13

dp is a problem solving technique which is used mostly in optimization problems and the main concept is to store the data i collect from the subproblems and the use these data to compose the solution to the main problem.
This problem though can be solved in a very easy way in O(n) without any sophisticated techniques

Answer 14

ok is it like u iterate over the array and copy the number of i's (0<i<n) in that array to another array nd list the items that are !=1?

Answer 15

like copy no.of i's to i'th index?

Answer 16

hmm... sort of.You actually think, what if the force could tell me the number of times 1,2,3,...,N appears in the sequence?Then the problem could be solved easily because you just have to list as duplicates the numbers which appear more than once and as missing the numbers that appear 0 times.Now, that i know what i could do if i had the force by my side, i can replace the force with a simple loop which counts the number of appearance of each element:

More precisely, consider an array A[N] which holds the sequence and A[i] is the i-th element on the sequence, know consider B[N] an other array whose all values are initially set to 0.

We iterate, and for every loop repetition we increase B[A[i]] where i is the loop counter.In that way we can pass through all the elements and count each number's appearance times.

And that's how we solve the problem. You can try to proove why the algorithm works or/and write a code in a programming language of your choice which implements the idea.

Answer 17

i was saying the same thing -.-
thanks anyway :) :D

Answer 18

ah.. ok, good job ;)