Question

in Java

A: Write a divide-and-conquer program to solve the following problem:

    1. Let A[1..n] and B[1..n] be two arrays of distinct integers, each sorted in an increasing order.

     2. Find the nth smallest of the 2n combined elements. Your program must run in O(log n) time.

For example:

n = 4
If A[1..n] = {2, 5, 8, 9} and B[1..n] = {1, 4, 6, 7}
The n^th (i.e. 4^th) smallest integer is 5.
If A[1..n] = {2, 5, 8, 13} and B[1..n] = {1, 9, 10, 15}
Then n^th smallest integer is 8.

B: Modify your program in A to find the k^th smallest number with k < n. Your program must run in O(log n) time.

For example:

n = 4 and k=3
If A[1..n] = {2, 5, 8, 9} and B[1..n] = {1, 4, 6, 7}
The k^th (i.e. 3rd) smallest integer is 4.
If A[1..n] = {2, 5, 8, 13} and B[1..n] = {1, 9, 10, 15}
Then k^th smallest integer is 5.

C: Modify your program in A to find the k^th smallest number when k > n by finding the j^th largest number in the 2n combined elements where j=2n-k+1. Your program must run in O(log n) time.

For example:

n = 4 and k=6

If A[1..n] = {2, 5, 8, 9} and B[1..n] = {1, 4, 6, 7}
The k^th (i.e. 6^th) smallest integer is also the jth (2*4-6+1=3rd) largest integer in the two combined arrays, which is 7.

Answer 1

A.

package demo;

import java.util.Scanner;

public class DemoTranslation {
   public static void main() {
       int n, temp;
       System.out.print("Enter the size of arrays:");
       n = STDIN_SCANNER.nextInt();
       int[] a = new int[n], b = new int[n], c = new int[2 * n];
       System.out.println("Enter the elements of array A");
       for(int i = 0; i < n; i++) {
           a[i] = STDIN_SCANNER.nextInt();
           c[i] = a[i];
       }
       System.out.println("Enter the elements of array B");
       for(int i = 0; i < n; i++) {
           b[i] = STDIN_SCANNER.nextInt();
           c[i + n] = b[i];
       }
       for(int i = 0; i < 2 * n; i++) {
           System.out.print(c[i] + " ");
       }
       for(int i = 0; i < 2 * n; i++) {
           for(int j = i + 1; j < 2 * n; j++) {
               if(c[i] > c[j]) {
                   temp = c[i];
                   c[i] = c[j];
                   c[j] = temp;
               }
           }
       }
       System.out.print("\n" + n + "th smallest element is " + c[n - 1]);
   }

   public final static Scanner STDIN_SCANNER = new Scanner(System.in);
}

For parts A and B, the same logic is applied. Just use the value of k accordingly.