Question

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

Answer 1

ALGORITHM

a) efficient algorithm to find the maximum difference between any two integers in the array

-->>Iterate through the array

-->>Find the maximum number and minimum number in the array

-->> Calculate Maximum - Minimum number

Time Complexity: O(n)

b.)

-->> Declare a variable to store the minimum difference and Initialize difference = infinite. This step takes O(1) time.

-->> Sort the array and iterate through the array, This step takes O(n logn) time.

-->> If the difference of adjacent elements is less than the minimum difference then update the minimum difference variable. This step takes O(n) time.

Time Complexity: O(nlogn)

c.)

-->> Iterate the array & Increment the frequency of the element in the HashMap /dictionary one by one

-->> Iterate through every key-value pair in the HashMap /dictionary

-->> If the frequency is more than (n+1)/2 then Print the element and break the loop

Time Complexity: O(n)

FOR CODE, DO LET ME KNOW THE LANGUAGE

******************************************************************************************
PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION
******************************************************************************************