K-th element of two sorted Arrays Java

PROGRAM TO FIND K-th ELEMENT OF TWO SORTED ARRAYS


class MAIN
{
 
    static int kth(int arr1[], int arr2[], int m,
                   int n, int k, int st1, int st2)
    {
        // In case we have reached end of array 1
        if (st1 == m)
        {
            return arr2[st2 + k - 1];
        }
 
        // In case we have reached end of array 2
        if (st2 == n)
        {
            return arr1[st1 + k - 1];
        }
 
        // k should never reach 0 or exceed sizes
        // of arrays
        if (k == 0 || k > (m - st1) + (n - st2))
        {
            return -1;
        }
 
        // Compare first elements of arrays and return
        if (k == 1)
        {
            return (arr1[st1] < arr2[st2])
                    ? arr1[st1] : arr2[st2];
        }
        int curr = k / 2;
 
        // Size of array 1 is less than k / 2
        if (curr - 1 >= m - st1)
        {
             
            // Last element of array 1 is not kth
            // We can directly return the (k - m)th
            // element in array 2
            if (arr1[m - 1] < arr2[st2 + curr - 1])
            {
                return arr2[st2 + (k - (m - st1) - 1)];
            }
            else
            {
                return kth(arr1, arr2, m, n, k - curr,
                        st1, st2 + curr);
            }
        }
 
        // Size of array 2 is less than k / 2
        if (curr - 1 >= n - st2)
        {
            if (arr2[n - 1] < arr1[st1 + curr - 1])
            {
                return arr1[st1 + (k - (n - st2) - 1)];
            }
            else
            {
                return kth(arr1, arr2, m, n, k - curr,
                        st1 + curr, st2);
            }
        }
        else
         
        // Normal comparison, move starting index
        // of one array k / 2 to the right
        if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1])
        {
            return kth(arr1, arr2, m, n, k - curr,
                    st1 + curr, st2);
        }
        else
        {
            return kth(arr1, arr2, m, n, k - curr,
                    st1, st2 + curr);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = {2, 3, 6, 7, 9};
        int arr2[] = {1, 4, 8, 10};
        int k = 5;
        int st1 = 0, st2 = 0;
        System.out.println(kth(arr1, arr2, 5, 4, k, st1, st2));
    }
}


OUTPUT
6

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more