if N <= 64 then we can convert all rows in an equivalent integer and then sort all numbers and print distinct No.s
else Worst case Solution would be to to check for each pair of rows and match - O(N^3) one more solution i can think of is to divide and conquer solution which goes like this based on the first bit of each row divide the matrix into 2 sub matrices, one with first bit as 0 and other with 1 and keep dividing the sub matrices further, as soon as a sub matrix contains single row that will be unique, and after all column's have been traversed if a sub matrix contains multiple rows that means they all are same. Recurrence of the algorithm can be written as follows (considering N rows, M columns and two sub matrix formed contains about half rows T(N,M) = 2T(N/2,M-1) + O(MN) i think TC for this will be O(N^2lgN)...not sure :) Any thing better we can do ?? -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
