**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:

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)

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

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.

@Bhavin

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

Post a Comment