Question

In this problem your task is to find a missing number. The input will always consist of an array of n positive integers such that the difference between every two consecutive numbers is a fixed constant but one integer is missing. See below for two example inputs/outputs: Input sequence: [0, 2, 4, 6, 10] Output: missing number is 8 Input sequence: [1, 4, 7, 13, 16] Output: missing number is 10 Note that in the first example the constant c is equal to 2 and in the second example the constant is equal to 3. You do not know before hand what the constant is. All you know is that c is just some positive integer.

1. Give an O(1)-time function to compute the constant c from any input list or array L

. 2. Give an O(n)-time algorithm to find the missing number (use the function from part (1)). Give pseudo-code and a short description.

3. Give an O(log n)-time divide-and-conquer algorithm to find the missing number (you also should use the function from part (1)). Give pseudo-code and a short description. Then give the recurrence relation and show that is solves to O(log n).

Answer #1

**1. Find constant c in O(1) time**

**Approach :** We cannot simply find difference
between first 2 numbers. Because there can be scenario where 2
number is the missing number example [0,4,6,8,10], Hence we can
find two difference and minimum of them is constant value.

int findConstant(Arr[1....N]):

a = Arr[2] - Arr[1]

b = Arr[3] - Arr[2]

c = min(a,b)

return c

**2. Find missing number in O(n) time
Approach :** We can simply traverse the array and check if
next number have difference = c, if not then it is the missing
number

int findMissingNumber(Arr[1...N]):

c = findConstant(Arr)

for i=1 to N-1:

if(Arr[i+1] != Arr[i]+c)

return Arr[i]+c

**3. Divide and conquer approach to find missing number in
O(logN) time**

**Approch :** We can break array in two parts and
decide which part to traverse based on whether missing number
exists in left/right subarray. At the end size of array reduces to
size of 2 where missing number lies between those two numbers

findMissingNumber(Arr[low...high], C):

start = Arr[low]

if(low+1 == high)

return start + C;

mid = low + (high - low)/2

number = start + (mid-low) * C

if(Arr[mid] > number)

return findMissingNumber(Arr[low...mid], C) // traverse
to left subarray

else

return findMissingNumber(Arr[mid...high], C) // traverse to right
subarray

Design a recursive divide-and-conquer algorithm A(n) that takes
an integer input n ≥ 0, and returns the total number of 1’s in n’s
binary representation. Note that the input is n, not its binary
representation. For example, A(9) should return 2 as 9’s binary
representation is 1001, while A(7) should return 3 since 7 is 111
in binary. Note that your algorithm should have a running time of
O(log n). Justify your answer. You need to do the following: (1)...

We are given an array A of size n containing n positive and
negative integers (the array is indexed starting from 0).
Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n
and Pk=j k=i A[k] is maximized.
Input sequence: [2, -4, 1, 9, -6, 7, -3]
Output: [1, 9, -6, 7] or i = 2 and j = 5
Input sequence: [1, 2, 3, 4, 5, 6, -3]
Output: [1,...

2. Design a deterministic algorithm to solve the following
problem.
input: An array A[1...n] of n integers.
output: Two different indices i and j such that
A[i] = A[j], if such indices exist.
Otherwise, return NONE.
Your algorithm must take O(n log(n)) time. You must describe your
algorithm in plain English (no pseudocode) and you must explain why
the running time of your algorithm is O(n log(n)).

1. Define the problem Closest-Pair as follows. • Input: an array
A consisting of distinct numbers. • Output: the numbers x, y in A
such that |x − y| is as small as possible. Design an O(n log n)
time algorithm for this problem
. Define the List-Delete problem as follows. • Input: A linked
list L of distinct integers and an element a of L. • Output: L with
the element a deleted. Design an O(1)-time algorithm for the...

Provide an algorithm that solves the following problem:
input: a binary heap B, an integer value x
output: all keys in B that are smaller than x
Constraint: your algorithm must run in time O(K), where K is the
number of keys output.
Explain why your algorithm has the required runtime
behaviour.
(Use pseudocode or C++, or any informal (but clear) description.
You are free to choose any kind of representation of binary heaps,
as long as it was mentioned...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

Divide-and-Conquer technique is famous for providing O(n log n)
solutions for problems with O(n2) straight forward
solutions. One of those problems is the “Maximum Subarray Sum” or
“Maximum Value Contiguous Subsequence": Given a sequence of n
numbers A[0 ... n-1], give an algorithm for finding a contiguous
subsequence A[i ... j], for which the sum of elements in this
subsequence is the maximum we can get by choosing different i or
j.
For example: the maximum subarray sum for the...

A speedy Decrease-and-Conquer search.
Use your newly acquired knowledge of “Decrease-and-Conquer”
algorithm design strategy to design a O( n ) algorithm to search
for a given number in an n × n matrix in which every row and every
column in this matrix is sorted in increasing order
Write your algorithm as an elegant java method named
findElement(int [][] arr, int element) that
returns the index of that element in the array as a small int array
made of 2...

Find the worst-case complexity of the algorithm below. Show your
work.
UFSizeCalc
Input: uf: Union-Find array
of size n
Input: n: size of uf
Output: size array for uf; that is, an
array s such that s[r] equals the number of
elements in the Union-Find tree rooted at r, for every
root r (s may have any value for indexes that are
not roots of uf)
Pseudocode:
For i = 1 to n
uf.Find(i)
size = Array(n)
Initialize size to be...

Please post all code in Pseudo code. Please post ORIGINAL
answers do not copy from similar questions. Please post in a format
that can be directly copied. Reasoning on answers would be most
helpful but not required. Thank you in advance for your help.
1.Design an algorithm to find all the common elements in two sorted
lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2,
3, 5, 5, 7, the output should be 2,...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 18 minutes ago

asked 18 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago