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 \))
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) \).
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. |