CODEWITHSUNDEEP
algorithmmodulus
Sohaib
Sohaib

Reputation: 4694

O(nlogn) algo to minimize abs(x+y)

I was asked a question in an interview I appeared in recently. I was not able to solve this problem. Interested people in algorithm design may like this problem.

Given an array of real numbers S, find a pair of numbers x&y in S that minimizes |x+y|. The algo for the same should be designed to run in O(nlogn).

I could not find a solution to this. Can anyone guide me in the right direction please to the solution of this problem? Any suggestions would be greatly appreciated.

Upvotes: 1

Views: 518

Answers (2)

ElKamina
ElKamina

Reputation: 7807

Sort the numbers. For each element x do a binary search for -x. You get the closest number y to minimize |x+y|.

Note: You can also optimize the second part. Start with indices for first and last element: i=0, j=n-1. At every iteration calculate the sum, update the minimum sum, and increment i if sum<0 or decrement j (when sum>=0).

Upvotes: 4

Brian Bulkowski
Brian Bulkowski

Reputation: 906

The question by the interviewer - or your restatment - seems to be lacking in two ways.

1) Real numbers are very, very hard to represent in a computer. They can be represented in symbolic format, or a subset as floating point, and subsets of real numbers (like the integers)

2) Mod takes two arguments, their statement is to minimize mod(x+y) instead of mod(x,y).

Could this have been an interview problem designed to challenge that the statement of the problem is wrong?

Wikipedia defines "mod" as "Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n." and "euclidian division" as "In arithmetic, the Euclidean division is the conventional process of division of two integers producing a quotient and a remainder. "

Further source that "mod" on real numbers doesn't make sense: http://www.abstractmath.org/MM/MMNumberTheory.htm

If the problem is defined as an array of integers minimizing mod(x,y) in O(nlogn), that seems tractable. You sort the array and for every element apply --- essentially --- a twist on a binary search for every pair. Doing a binary search over mod-space is left to the reader, as one would say.

I have several interview questions I use in the same way, finding out whether a candidate has the guts to question the question. This question might have the elements of both, having to question the idea of reals and mod on reals, then solving a tractable problem (a fairly traditional search data structure problem).

When I give those questions, the first part can be kind of a "gotcha" question, and I'll let them puzzle over that issue for a few minutes, and then re-present the problem as a tractable problem, just to move the interview along.

Upvotes: 1

Related Questions