Given an unsorted array A[1...n] of distinct integers numbers and is given a non

Question

Given an unsorted array A[1...n] of distinct integers numbers and is given a nonnegative integer number, k, k < n. You need to find an element from A such that its rank is k, i.e., there are exactly (k-1) numbers less than or equal to that element.

Example: Input: A = [1, -3, 4, 3, 12, 20, 30, 7, 14, -1, 0] and k =8.

Output: 12, since 7, -3, -1, 0, 4, 3, 1 (8-1=7 numbers) are all less than or equal to 12

Suggest a sub-quadratic running time complexity algorithm (only pseudo code) to solve this problem. Justify.

Explanation / Answer

writing the code in java

import java.util.Scanner;
import java.util.Arrays;

public class HelloWorld{

public static void main(String []args){

int A[] = {1, -3, 4, 3, 12, 20, 30, 7, 14, -1, 0};
Scanner sc = new Scanner(System.in);
System.out.println("Enter any integer");
int num = sc.nextInt();
Arrays.sort(A);
if(num < A.length)
{
System.out.println(" "+A[num-1]);   
}
else{
System.exit(0);
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.