-2

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

necromancer
  • 33
  • 6
  • 6
    good luck with your home work, tell us if you got a real programmatic problem – No Idea For Name Sep 08 '13 at 05:50
  • 1
    possible duplicate of [How to find the kth largest element in an unsorted array of length n in O(n)?](http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on) – Blender Sep 08 '13 at 05:52
  • You can't do it in O(log(n)) time. If the array is unsorted, you will have to look at every element once, which is O(n). – Blender Sep 08 '13 at 05:56
  • @Blender - I Read the link you suggested , but i guess that applies to questions in which you are provided with the value of "k". Here value of "k" is not provided, we have to find the value of "k" – necromancer Sep 08 '13 at 05:57
  • yes O(logn) is not possible :) – necromancer Sep 08 '13 at 06:01
  • is there any possibilities of duplicate numbers? – stinepike Sep 08 '13 at 06:03
  • @stinePike I m not sure about that. Lets assume we can have duplicates. :) . If there's a solution without duplicates then please share :) – necromancer Sep 08 '13 at 06:08
  • It's a trivial change in the algorithm for order statistics, as Blender said. Hint: in the original algorithm, you check of the current pivot is at the kth position; if not, you recurse on the side of the pivot that contains the index k; instead, try checking if the pivot satisfies your new condition (`k=n - pivot value`), and otherwise which side can contain the solution. – DanielKO Sep 08 '13 at 06:15

2 Answers2

0

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);

}
necromancer
  • 33
  • 6
  • Where is `k` in this algorithm? What are the bounds of your arrays? Also please refer to the source. – gaborsch Sep 08 '13 at 08:39
  • Output printed is the "k". Value of "k" is not given before hand, we have to find it. Input array is a[1..n] – necromancer Sep 08 '13 at 09:01
  • There is no way this works as written. Ignoring the obvious problem of negative integers in the array, here's a counter example: [ 2, 5, 6 ]. Your count[0..3] array will look like [ 0, 1, 0, 2 ], and you won't output the correct answer '2'. You're on the right track though. – Judge Mental Sep 21 '13 at 08:22
0
int[] count = new int[ n + 2 ];
for ( int k = 0; k < n; ++k )
    ++count[ Math.min( n + 1, Math.max( 0, a[ k ] + 1 ) ) ];
int k = n, c = count[ n + 1 ];
for ( ; k > 0 && ( 0 == count[ k ] || k != c ); c += count[ k-- ] );
System.out.println( 0 == k ? "not found" : "found: " + k );
Judge Mental
  • 5,209
  • 17
  • 22