Find the Element Occurring b times in an an array of size n*k+b

Question

Description

Given an Array of size (n*k+b) where n elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 < b < k find the element occurring b times.

My Attempted solutions

1. Obvious solution will be using hashing but it will not work if the numbers are very large. Complexity is O(n)

2. Using map to store the frequencies of each element and then traversing map to find the element occurring b times.As Map's are implemented as height balanced trees Complexity will be O(nlogn).

Both of my solution were accepted but the interviewer wanted a linear solution without using hashing and hint he gave was make the height of tree constant in tree in which you are storing frequencies, but I am not able to figure out the correct solution yet.

I want to know how to solve this problem in linear time without hashing?

EDIT:

Sample:

Input: n=2 b=2 k=3

Aarray: 2 2 2 3 3 3 1 1

Output: 1

Answer 1

I assume:

1. The elements of the array are comparable.
2. We know the values of n and k beforehand.
3. A solution O(n*k+b) is good enough.

Let the number occuring only b times be S. We are trying to find the S in an array of n*k+b size.

Recursive Step: Find the median element of the current array slice as in Quick Sort in lineer time. Let the median element be M.

After the recursive step you have an array where all elements smaller than M occur on the left of the first occurence of M. All M elements are next to each other and all element larger than M are on the right of all occurences of M.

Look at the index of the leftmost M and calculate whether S<M or S>=M. Recurse either on the left slice or the right slice.

So you are doing a quick sort but delving only one part of the divisions at any time. You will recurse O(logN) times but each time with 1/2, 1/4, 1/8, .. sizes of the original array, so the total time will still be O(n).

Clarification: Let's say n=20 and k = 10. Then, there are 21 distinct elements in the array, 20 of which occur 10 times and the last occur let's say 7 times. I find the medium element, let's say it is 1111. If the S<1111 than the index of the leftmost occurence of 1111 will be less than 11*10. If S>=1111 then the index will be equal to 11*10.

Full example: n = 4. k = 3. Array = {1,2,3,4,5,1,2,3,4,5,1,2,3,5} After the first recursive step I find the median element is 3 and the array is something like: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} There are 6 elements on the left of 3. 6 is a multiple of k=3. So each element must be occuring 3 times there. So S>=3. Recurse on the right side. And so on.