CODEWITHSUNDEEP
carrays
Benjamin Crouzier
Benjamin Crouzier

Reputation: 41905

How to pick two numbers based on if their difference is closest to a given number?

I have the following code:

float difference = 6.5;
float values[] = {1.3, 7.0, 6.4, 15.1};
float min;
float max;

I want to assign min and max so that their difference max-min is closest to difference. In this case, min should be 1.3 and max 7.0.

How can I do that ?

Upvotes: 2

Views: 188

Answers (2)

Luchian Grigore
Luchian Grigore

Reputation: 258618

O(n) solution, assuming the array is sorted and n is the focal difference:

Start off with two iterators at both ends of the array: i and j.

1) Check differences j-i, (j-1)-i, j-(i+1).

2) If the minimum is j-i, you found the answer.

Proof: If j-i is closer to n than (j-1)-i, it will be closer to n than (j-k)-i.

3) If (j-1)-i is closest, move iterator j to j-1 go to 1).

4) If j-(i+1) is closest, move iterator i to i+1 go to 1).

A run on your example:

  i               j
{1.3, 6.4, 7.0, 15.1}

j-i     = 13.8
(j-1)-i = 5.7
j-(i+1) = 8.7

Move iterator j one position left:

  i         j      
{1.3, 6.4, 7.0, 15.1}

j-i     = 5.7
(j-1)-i = 5.1
j-(i+1) = 0.6

Return current results, since j-i = 5.7 is closest.

Upvotes: 1

Gabriel Belingueres
Gabriel Belingueres

Reputation: 2985

In this code fragment the min and max are indexes into the array:

int min=-1; 
int max=-1;
float mindiff = FLT_MAX;
for(int i=0; i < arraylength; ++i) {
    for(int j=i+1; j < arrayLength; ++j) {
        float diff = abs((max(values[i],values[j]) - min(values[i],values[j])) - difference);
        if (diff < mindiff) {
            if (values[i] < values[j]) {
               min = i;
               max = j;
           }
           else {
               min = j;
               max = i;
           }
           mindiff = diff;
       }
    }
}

Upvotes: 0

Related Questions