You have an array of size '2n' of these, 'n+1' elements are distinct and 1 element is repeated 'n' times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?

cullensun

 Profile Answers by cullensun Questions by cullensun

• Sep 23rd, 2013

1st, 2nd, 3rd,......, (n-1)th, (n)th, (n+1)th, (n+2)th, ...... (2n)th Focus: Identify the the repeated element 1. take the 1st element to compare with the rest one by one, worst case: compare wi...

shankar

• Oct 16th, 2012

Since an element is repeated more than half the occurance of the array, for every two didtinct elements discard them from the array. At the end of the loop, the most repeated element will be left.

This is O(n)

Answer Question  Select Best Answer