Question

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?

Java Language....

Answer 1

import java.util.Scanner;

public class solve {
    public static void findSumPairs(int[] array, int wantedSum) {
        recursiveSumPairs(array,  0, 1,wantedSum);
    }

    private static void recursiveSumPairs(
            int[] array,
            int firstIndex,
            int nextIndex,int wantedSum) {

        // Base Case for recursion: first element is the last
        // element in the array. This also handles input arrays shorter than
        // two elements.
        if (firstIndex >= array.length - 1) {
            System.out.println("No such pair exists");
            return;
        }

        // Increment the first index to the
        // next index and compare it to the rest of the elements ofthe
        // array.
        if (nextIndex >= array.length) {
            recursiveSumPairs(array, wantedSum, firstIndex + 1, firstIndex + 2);
            return;
        }

        if (array[firstIndex] + array[nextIndex] == wantedSum) {
            System.out.println(array[firstIndex] + " + " + array[nextIndex]);
        }

        // Compare first element to the next element in the array.
        recursiveSumPairs(array, wantedSum, firstIndex, nextIndex + 1);
    }


    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int []arr = new int[n];
        for(int i =0 ; i < n ;i ++)
            arr[i] = scn.nextInt();
        int sum = scn.nextInt();
        findSumPairs(arr,sum);

    }
}

Since this algorithm checks one element with every other element, the running time will be O(n^2) .

Please ask if you have any doubt , I used Divide and Conquer using recursion , i.e., I broke down the array into two parts in every iteration, one part contained one element and it was used to compare with other elements of the array.