Question

In: Computer Science

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?

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

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

Python - You are given a sorted (from smallest to largest) array A of n distinct...

Python - You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative or zero. Design the fastest algorithm you can for deciding if there is an index i such that A[i] = i.

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...

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