Software Developer

This is a two-step process:

The first step gives the element that may be the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.
Check if the element obtained from the above step is the majority element. This step is necessary as there might be no majority element.

ee, here each coin of a given denomination can come an infinite number of times. (Repetition allowed), this is what we call UNBOUNDED KNAPSACK. We have 2 choices for a coin of a particular denomination, either i) to include, or ii) to exclude. But here, the inclusion process is not for just once; we can include any denomination any number of times until N<0.

Basically, If we are at s[m-1], we can take as many instances of that coin ( unbounded inclusion ) i.e count(S, m, n – S[m-1] ) ; then we move to s[m-2]. After moving to s[m-2], we can’t move back and can’t make choices for s[m-1] i.e count(S, m-1, n ).

Finally, as we have to find the total number of ways, so we will add these 2 possible choices, i.e count(S, m, n – S[m-1] ) + count(S, m-1, n ) ; which will be our required answer.

Algorithm: 
Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s
Traverse through the array and increase the count of c0 if the element is 0,increase the count of c1 if the element is 1 and increase the count of c2 if the element is 2
Now again traverse the array and replace first c0 elements with 0, next c1 elements with 1 and next c2 elements with 2.

We can also use Max Heap for finding the k’th smallest element. Following is an algorithm. 
1) Build a Max-Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of MH. 
……a) If the element is less than the root then make it root and call heapify for MH 
……b) Else ignore it. 
// The step 2 is O((n-k)*logk)
3) Finally, the root of the MH is the kth smallest element.
Time complexity of this solution is O(k + (n-k)*Logk)

we can use a max heap on the left side to represent elements that are less than effective median, and a min-heap on the right side to represent elements that are greater than effective median.

After processing an incoming element, the number of elements in heaps differs utmost by 1 element. When both heaps contain the same number of elements, we pick the average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of the heap containing more elements.