Find if number occurs exactly n/2 times in an array

You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?

Expected time complexity : O(n)
Expected space complexity : O(1)

What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)

Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html

4 comments:

Madhur Kumar Tanwani said...

We need 3 pointers :
ptr1 -> first element
ptr2 -> second element
ptr3 -> third element

while(end of array is reached) {
 if(any one of ptr1/2/3's value is equal) {
   then return the match
 }
 else
 {
   ptr1<-ptr2<-ptr3<-next element
 }
}

Time complexity : O(n)
Space : O(1)

Madhur Kumar Tanwani said...

Another interesting solution could also be (got this from an interview discussion) :

1.> Make the input data circular (array / list - data storage / representation)

2.> Do a adjacency check - two a's together

3.> Do a distance = 1/2 check - two separated by one/two char

Bhavin Shah said...

I've another soln, I havnt thought it through but I think it meets req.

1. Create an array of 10, its each index stores the count for number of times no from 0-9 appears.
2. Create a similar array to store character occurrences.
3. Now traverse the list zero to end and keep updating the counter corresponding to each character.
4. In the end you should have count for all, you can just traverse the list again to check if any of it is n/2.

Madhur Kumar Tanwani said...

@Bhavin
Solution will work for characters & digits - not for numbers / strings etc..

 
Stats