Suppose you are given an n-element array containing distinct integers that are listed in increasing order....

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?

Solutions

Expert Solution

In the above question, since the integers are in an increasing order, we can deduce that they are sorted already.

Now we need to find the complexity of finding the two integers whose sum can be k, if such pair exists.

The best approach would be that we start comparing the two elements in loop. starting from first and last element.

Lets refer to below code to see how to do this:

Eg: Our array is { 2,3 ,5, 7,9 }, k=16

Now I take the first element-2 and last element 9

2+9=11 which is less than 16.

So I move one element ahead from the left side which is the second element ->3

3+9=12 which is less than 16.

So I move one element ahead from left again.->5

9+5=14 which is than 16.

Again I move 1 ahead-> 7

7+9=16. Now we find a pair which has such pair of element.

Now what will be the complexity?

At worst case we will have to traverse the whole array till the end.

If there are n elements, then complexity will be O(n).

venereology answered 1 year ago

Next > < Previous

Related Solutions

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing...

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....

An array A[0..n - 2] contains n-1 integers from 1 to n in increasing order. (Thus...

An array A[0..n - 2] contains n-1 integers from 1 to n in increasing order. (Thus one integer in this range is missing.) Design an algorithm in (Theta(log n)) to find the missing integer. Your algorithm should be given in pseudo code. For example, the array A could be {1, 2, 3, 4, 6, 7, 8, 9, 10} in which 5 is missing.

Consider an array of length n containing positive and negative integers in random order. Write the...

Consider an array of length n containing positive and negative integers in random order. Write the C++ code that rearranges the integers so that the negative integers appear before the positive integers. write a program that includes both functions and a main() function that tests them. Name the two functions rearrangeN() and rearrangeN2().

1. Given an array of integers a dimension n. If the array contains the same number...

1. Given an array of integers a dimension n. If the array contains the same number of even and odd elements get (a1 + an) (a2 + an-1) ... 2. Given an array of integers dimension n. All array elements with even numbers preceding the first element to the maximum, multiplied by the maximum. 3. Given an array of dimension n. Insert after each zero element of the element in the middle (or the amount of secondary elements for even...

Given an array of integers and the size of the array, write a function findDuplicate which prints the duplicate element from the array.

C++ Programming using iostream and namespace stdGiven an array of integers and the size of the array, write a function findDuplicate which prints the duplicate element from the array. The array consists of all distinct integers except one which is repeated. Find and print the repeated number. If no duplicate is found, the function should print -1. void findDuplicate (int [ ], int)Example 1: Given array: {2,3,5,6,11,20,4,8,4,9} Output: 4 Example 2: Given array: {1,3,5,6,7,8,2,9} Output: -1

Given an array of integers, delete each element from the array which is a multiple of 5, and display the rest of the array.

Given an array of integers, delete each element from the array which is a multiple of 5, and display the rest of the array.Input: 6 2 3 4 11 22 320 where:First line represents the number of elements in the array.Second line represents the elements in the array.Output: 2 3 4 11 22Explanation: Element of the array 320 is the only one in the array which is a multiple of 5, so it is removed from the array.Assumptions:Array can be of size...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...

How would you take a given array of non-repeating random integers and sort every 5th element. Meaning index 0 is the smallest element in the array.

JAVA ProgrammingHow would you take a given array of non-repeating random integers and sort every 5th element. Meaning index 0 is the smallest element in the array. index 4 is the 5th smallest element in the array, index 9 is the 10th smallest element in the array and so on...- this array could be small (like 5 indexes) or large (like 100,000 indexes).- all other numbers do not change position

Given an array A of n distinct real numbers, we say that a pair of numbers...

Given an array A of n distinct real numbers, we say that a pair of numbers i, j ∈ {0, . . . , n−1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b)...

Given an array A of n distinct numbers, we say that a pair of numbers i,...

Given an array A of n distinct numbers, we say that a pair of numbers i, j ∈ {0, . . . , n − 1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Define the Inversion problem as follows: • Input: an array A consisting of distinct numbers. • Output: the number of inversions of A, i.e. |inv(A)|. Answer the following:...

Subjects