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 9 months ago

Next > < Previous

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

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

1) Write a function searchValue that accepts an array of integers, the size of the array,...

1) Write a function searchValue that accepts an array of integers, the size of the array, and an integer. Find the last occurrence of the integer passed in as an input argument in the array. Return the index of the last occurrence of the value. If the value is not found, return a -1 2) Write the line of code to call the previous function assuming you have an array vec with length n, and are looking for the number...

Array indices must be positive integers or logical values?

How can I fix this MATLAB error Index in position 2 is invalid. Array indices must be positive integers or logical values?

Which positive integers n, where 20 ≤ n ≤ 30, have primitive roots?

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

Subjects