Median Queries:- a subarray of A of length , you have to sort the elements of the subarray in a non-decreasing order

Question

You are given an array A consisting of N elements. For a subarray of A of length len, you have to sort the elements of the subarray in a non-decreasing order. The element at the position ceil(len/2) is called the median of the subarray. Consider the array and each subarray to be 1 indexed.

Write a program to answer Q queries of the following types:

You are given two integers L and R. You have to find the median of a subarray A_L, A_{L+1},..., A_R of the array A.

Input format

• First line: N
• Second line: N space-separated integers (denoting the array A)
• Third line: Q
• Next Q lines : Two space-separated integers L and R

Output format:

For each query, print the median of the subarray.

Constraints

1 ≤  N, Q ≤  5 * 10^4
1 ≤ A_i ≤ 10^9
1 ≤ L ≤ R ≤ N

Example

Input:

int[] A = {2,4,5,3,1,6};
int N = 6;

Output: 3, 4, 5

My attempt

I have tried:

private static final int generous = 1;
private static int median(int[] arr) {
    Arrays.sort(arr);
    int mid = arr.length / 2;
    if (mid + mid == arr.length) {
        return (arr[mid-1] + arr[mid] + generous) / 2;
    } else {
        return arr[mid];
    }
}

then just call it for each sub-array:

private static int[] getMedian(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        result[i] = median(Arrays.copyOfRange(arr, 0, i+1));
    }
    return result;
}

Answer 1

I have tried below code and it's working fine now:-

import java.util.Arrays;

public class MedianQueries {
    private static int median( int N, int[] A) {
        int[] arr = Arrays.copyOfRange(A,0,A.length);
        Arrays.sort(arr);
        int mid = (int) Math.ceil(N / 2);
        if (mid + mid == arr.length) {
            return arr[mid-1];
        } else {
            return arr[mid];
        }
    }

    private static void getMedian(int[] A){
        while (A.length >=1) {
            System.out.println(median(A.length, A));
            int mid = (int) Math.ceil(A.length/2);
            A = Arrays.copyOfRange(A, 1, mid+1);
        }
    }
    
    public static void main(String args[] ) throws Exception {
        int[] A = {2,4,5,3,1,6};
        getMedian(A);
    }
}