Problem 4. Given a set of n integers, you have to compute the closest pair of in

Question

Problem 4. Given a set of n integers, you have to compute the closest pair of integers. Thus if the integers are 3, 71, 6, 8, 70, then the closes pair is (70, 71). To find such the closest pair of integers, follow these two steps: (Step 1) Sort the n integers in the ascending order. You need not do this part, but just assume that it can be done in O(n log n) steps. (Step 2) Starting from the sorted list obtained via step 1, design an algorithm to compute the closest pair from the sorted list. This is your task. What is the overall complexity of the entire algorithm?

Explanation / Answer

Since we have number in ascending order.
Claim 1: The closest pairs will be neighbours.
Proof :- since we have to the difference between two numbers to be minimum for the closest pairs. that can only we made if we choose two numbers which are neighbours to each other.

Here is code for the same:

let the Given set is S.

s = Sorted(s)
i = 1
min = INFINITY
num_1 = -1
num_2 = -1
while (i < len(s)):
   d = s[i] - s[i-1]
   if (d < min):
       min = d
       num_1 = i-1
       num_2 = i
   i += 1
print (num_1,num_2)

Overall Time Complexity:
   O(n log n) for sorting
   O(n-1) above while loop
   => O(n log n) + O(n) is overall Time Complexity
   => O(n log n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.