Question
In: Computer Science
We have an array A of size n. There are only positive integers in this array....
- We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity. a. Design an efficient algorithm to find the maximum difference between any two integers in the array. b. Design an efficient algorithm to find the minimum difference between any two integers in the array. If there are multiple minimum differences, you only need to find one. c. Design an efficient algorithm to find the majority number in the array if it exists. By majority, I mean the number that occurs more than half the time in the array or ⌈(?+1)/2 ⌉ (there are at least 3 ways that I can think of to approach this).
Solutions
Expert Solution
a. Design an efficient algorithm to find the maximum difference between any two integers in the array.
- For this we parse array one time and find minimum and maximum integer in array.Than we can find difference of both.This can be done in running loop 1 time. So overall time complexity is O(N).
b. Design an efficient algorithm to find the minimum difference between any two integers in the array.
- We will sort array in ascending order. Sorting will take O(NlogN) time. Then we comapre all adjecent pairs in sorted array and find min difference. This step will take O(N) time. So overall time complexity is O(NlogN).
c. Design an efficient algorithm to find the majority number in the array if it exists.
- We will sort the array. Sorting will take O(NlogN) time. Then
we will create a variable count and prevElement.We will traverse
the array. If the current element is equal to the previous element
increase the count. Else set the count to 1. If the value of count
is greater than half the size of array then it is the majority
number.
- Time Complexity = O(NlogN).
Like, if this helped :)
venereology answered 1 year agoRelated Solutions
We have an array A of size n. There are only positive integers in this array....
We have an array A of size n. There are only positive integers
in this array. Note that the array may have integers that are not
distinct, and it could be any array of positive integers in
creation (I like the numbers found the decimal expansion of π for
instance). When possible provide the exact complexity of the
algorithm. If it’s not possible explain the O/Ω/Θ complexity. a.
Design an efficient algorithm to find the maximum difference
between any two...
1. We have an array A of size n. There are only positive integers in this...
1. We have an array A of size n. There are only positive
integers in this array. Note that the array may have integers that
are not distinct, and it could be any array of positive integers in
creation (I like the numbers found the decimal expansion of π for
instance). When possible provide the exact complexity of the
algorithm. If it’s not possible explain the O/Ω/Θ complexity.
Design an efficient algorithm to find the maximum difference
between any two...
1. We have an array A of size n. There are only positive integers in this...
1. We have an array A of size n. There are only positive
integers in this array. Note that the array may have integers that
are not distinct, and it could be any array of positive integers in
creation (I like the numbers found the decimal expansion of π for
instance). When possible provide the exact complexity of the
algorithm. If it’s not possible explain the O/Ω/Θ complexity.
Design an efficient algorithm to find the maximum difference
between any two...
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...
Given an unsorted array A of size N of integers, find a continuous sub-array which adds...
Given an unsorted array A of size N of integers, find a
continuous sub-array which adds to the given number. Declare
dynamic arrays and use only pointers syntax. (no [ ]'s or (ptr+1)
stuff.
input will be the number of input values to enter followed by
the sum to compare with. print out the continuous sub-array of
values that are equal to sum or the message 'no sum ofund.'
there may be more than one sub-array to be found in...
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of
integers. We presented an O(n log n)-time algorithm in class and,
also, proved a lower bound of Ω(n log n) for any comparison-based
algorithm.
2. Give an efficient sorting algorithm for an array C[1, ..., n]
whose elements are taken from the set {1, 2, 3, 4, 5}.
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of
integers. We presented an O(n log n)-time algorithm in class and,
also, proved a lower bound of Ω(n log n) for any comparison-based
algorithm.
3. Give an efficient sorting algorithm for an array D[1, ..., n]
whose elements are distinct (D[i] ̸= D[j], for every i ̸= j ∈ {1,
..., n}) and are taken from the set {1, 2, ..., 2n}.
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of
integers. We presented an O(n log n)-time algorithm in class and,
also, proved a lower bound of Ω(n log n) for any comparison-based
algorithm.
1. Give an efficient sorting algorithm for a boolean1 array
B[1, ..., n].
2. Give an efficient sorting algorithm for an array C[1,...,n]
whose elements are taken from the set
{1,2,3,4,5}.
3. Give an efficient sorting algorithm for an array D[1, ...,
n] whose elements...
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().
On a circular array with n positions, we wish to place the integers 1, 2, ......
On a circular array with n positions, we wish to place the
integers 1, 2, ... r in order, clockwise, such that consecutive
integers, including the pair (r,1) are not in adjacent positions on
the array. Arrangements obtained by rotation are considered the
same. In how many ways can this be done? Give a combinatorial
proof.
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- A shrink-fit process has been used to enhance the pressure carrying capacity of a cylinder. During...
- Ten-year zero coupon bonds issued by the U.S. Treasury have a face value of $1,000 and...
- The Blossom Department of Transportation has issued 25-year bonds that make semiannual coupon payments at a...
- Please answer all 4 parts of this question John Johnson just received a cash gift from...
- Question #1 C4H10O with a butanol combustion cycle (formation enthalpy-332,000 kJ / kmol) 25 per cent...
- Suppose a survey revealed that 19% of 494 respondents said they had in the past sold...
- Topic: Choose a company which are you are starting, and a main product or service that...
ADVERTISEMENT