For a set S of n real numbers, a pair of elements x, y belong to S, where x < y, are said to be close if y – x <= ( max(S) – min(S) ) / (n-1) Suppose you are given an unsorted array A[1 : n] of distinct real numbers. Design an algorithm that finds a pair of close numbers in A in O(n) time.
my solutions 1. brute force: complexity n2 2. sort the array. take 2 ptrspt1 and pt2.initially pt1 points to 1st elementand pt2 pts to 2nd element. check if they are close nos. case1; if they r closeincrement pt2. and again check. repeat this until u find close pairs. when pt1and pt2 doesnt pt to close pairat this point all elements b/w pt1 and pt2 are also close. increment close_pair_count accordingly, check if element jst b4 pt2 and at pt2 are also close. case 2: increment both pt1and pt2 and continue repeat above steps til u reach end of array.. m unable to think linear algo.please help.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
