Q:

Find a element "k" such that there are "k" greater elements than this element in the unsorted array

Accolite Interview: 
Input: Array of integers (no range given) , unsorted , size n
Output: Find a element "k" in the array, such that there are exactly "k" elements in the array which are greater than this element. 
For example if the array is :
1.
[4,3,6,9,10,22]
Output here is 4
2.
[4,3,6,9,10]
output: No such number found
This question can be done very easily by sorting in O(n log n) Time , but i was asked to do it in O(n) time (and if O(logn) possible). 

A:

Someone helped , here's the solution
Point to note : "K" cannot be greater than size of the array. 
    We will have a count array of size equal to given array. 
assuming indexes start from 1 
for(i=1;i<=n;i++)
{
  if(a[i]<=n)
    count[a[i]-1]++;
  else
    count[n]++;
}

boolean flag=false;
 for(i=n-1;i>=1;i--)
 {
    if(count[i]==i)
    {
      flag=true;
      System.out.println("k: "+i);

    }
 }

 if(flag==false)
      System.out.println("No such number found);

}

