Find element occurring k2 times in an array sized (n x k1)+k2
  • timecomplexity
  • lineartime
  • array
  • searching
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (1895)

Suppose you are given an unsorted array of size \( (n \times k_1)+k_2 \) where n elements occur \( k_1 \) times and one element occurs \( k_2 \) times. Design a linear time algorithm to find the element occurring \( k_2 \) times without using any other data structure.(\( 0 < k_2 < k_1 \))


Posted Answers

In the input array, \( n_1 \) elements occur \( k_1 \) times and one element occurs \( k_2 \) times. There are n+1 distinct elements in the array of size \( (n_1 \times k_1+k_2) \).


  • Find the median of the input array of size \( (n \times k_1)+k_2 \) such that the elements smaller than median occur on the left of the first occurrence of median, all median elements are next to each other and the elements larger than median are on the right of all occurrences of median.
  • Look at the size of the subarray before the first occurrence of the median and after the last occurrence of the median.
  • If the size of the first subarray is a multiple of \( k_1 \), the element we are looking for will be at the second subarray. Repeat the first two steps recursively on the second subarray.
  • If the size of the second subarray is a multiple of \( k_1 \) , the element we are looking for will be at the first subarray. Repeat the first two steps recursively on the first subarray.


Example - Let the input array be [ 1 2 3 2 1 3 4 1 4 2 4 3 1 2 4 ] with \( k_1=4 \) and \( n_1=3 \).

Median of the array is 2 and the array looks like [ 1 1 1 1 2 2 2 2 3 3 4 4 4 3 4 ].
Since the first subarray is a multiple of \( k_1 \), the element we are looking for will be in the second subarray.

Similarly, in the second subarray median will be 4 and the array looks [
3 3 3 4 4 4 4
].
Thus 3 is the answer which occurs \( 3 ( k_2 \)) times.

Time complexity = \( O(n_1 \times k_1+k_2) \) which is linear.

You need to Sign In to post your solution.