Solved

Posted on 2009-02-23

Given an array of 15 numbers (already sorted Ascending) I need to find the 5 closest-together numbers. That is, the 5 numbers with the least total range between them.

For example, 1,2,3,4,5 have small range of 4, whereas 100,200,300,400,500 have a large range of 400.

I can brute force it with a loop like the attached code

but I wondering if there way a more elegant algorithm I could use, because once I get this working I could be looking through an array as large as 1000 numbers

trying to find the 5 'closest together' numbers.

Given the following array, my brute force finds elements 2-6 with a range of 12 to be the closest together set of 5.

array[0]=216;

array[1]=291;

array[2]=315;

array[3]=316;

array[4]=320;

array[5]=326;

array[6]=327;

array[7]=384;

array[8]=412;

array[9]=467;

array[10]=589;

array[11]=602;

array[12]=662;

array[13]=663;

array[14]=709;

For example, 1,2,3,4,5 have small range of 4, whereas 100,200,300,400,500 have a large range of 400.

I can brute force it with a loop like the attached code

but I wondering if there way a more elegant algorithm I could use, because once I get this working I could be looking through an array as large as 1000 numbers

trying to find the 5 'closest together' numbers.

Given the following array, my brute force finds elements 2-6 with a range of 12 to be the closest together set of 5.

array[0]=216;

array[1]=291;

array[2]=315;

array[3]=316;

array[4]=320;

array[5]=326;

array[6]=327;

array[7]=384;

array[8]=412;

array[9]=467;

array[10]=589;

array[11]=602;

array[12]=662;

array[13]=663;

array[14]=709;

```
keystart=0;
range=array[4]-array[0];
for(start=1;start<=10;start++){
if ((array[start+4]-array[start])<range){
range=array[start+4]-array[start];
keystart=start;
}
}
```

13 Comments

However, if fuzziness is allowed, or when it is ok to be imprecise in a way, then you can use a divide and conquer style algorithm, or just loop every fifth element.

Speeding things up a bit will differ on the data. You can put in some logic where if you have two elements that are already too far apart as the current lowest - 3, you can skip the next three. But be aware, you might need to go back if the following two (after skipping) are low enough to make a low - 3 sum complete. You could mark positions that way and go back later, because it is likely that you will have a five-combi that will defeat those jumps.

Note that looping an array of 1000 numbers is not such a big deal considering the opcodes needed. Any modern computer can do an array of 1 million integers and do a compare on each of them in less then a tenth of a second (depending on language / interpreter / compiler).

There is no need for any more than a single-pass 'scan' of the array.

Your loop loops from 0 through n-6 (n-5-1) where 'n' is the nukmber of elements in the array, -5 is the 'range' offset and -1 because we're starting from 0 rather than 1.

Something like...

range = array(4) - array(0);

keystart = 0;

for (i = 0, i < (n - 4), i++) {

if (array(i + 4) - array(i)) < range {

range = array(i + 4) - array(i);

keystart = i;

}

}

The only problem with this code is it performs the 'array(i + 4) - array(i)' twice and this is wasteful. It may be better to asign the result of this calculation to an temporary variable and then use the this in the 'if' statement as in:

range = array(4) - array(0);

keystart = 0;

for (i = 0, i < (n - 4), i++) {

temp = array(i + 4) - array(i);

if temp < range {

range = temp;

keystart = i;

}

}

You may find this performs faster on a large array. In terms of elegance, this would be the best solution.

There is no 'elegant' solution to this problem. This can only be solved using iteration as you have already shown.

There is no need for any more than a single-pass 'scan' of the array.

Your loop loops from 0 through n-4 (n - 4) where 'n' is the nukmber of elements in the array, and -4 is the 'range' offset.

Something like (which is similar to your code)...

range = array(4) - array(0);

keystart = 0;

for (i = 0, i < (n - 4), i++) {

if (array(i + 4) - array(i)) < range {

range = array(i + 4) - array(i);

keystart = i;

}

}

However, the only problem with this code is it performs the 'array(i + 4) - array(i)' twice and this is wasteful. It may be better to asign the result of this calculation to an temporary variable and then use the this in the 'if' statement as in:

range = array(4) - array(0);

keystart = 0;

for (i = 0, i < (n - 4), i++) {

temp = array(i + 4) - array(i);

if temp < range {

range = temp;

keystart = i;

}

}

You may find this performs faster on a large array. In terms of elegance, this would be the best solution.

PS. I'm not going to quibble for starting my loop fro 0 rahter than 1 as you have done. In fact, it makes the logic seem clearer as we're reminded the first element of our array is 0.

```
int temp[5];
k = 0
keystart = 0
range = +infinity // or the biggest possible finite value
for (i=0; i<n; ++i) {
t = array[i]
if (i>4) {
d = t-temp[k]
if (d<range) {
range = d
keystart = i-4
}
}
temp[k] = t
if (k==4) k=0; else ++k; // thus always k = i % 5
}
```

I don't think you can make it any simpler, slicker nor elegant as it already stands.... I couldn't get to grips with your solution. Are you trying to implement some sort of read-ahead 'buffer'?

Yeah I wasn't having any speed problems, I just saw myself bruting through and thought there might be a better way.

I'm not exactly sure how to close this question.

Or split the points between the persons giving useful information for you to take this conclusion

In my post ID: 23715981, I compared my code (which I wrote from the ground up) and compared it to your own code.

They are almost identical (save for the names of variables etc)

I then went on to suggest an improvement which you don't seem to have picked up on so I will now use your own code and moedl it after mine. Please see solution below:

keystart = 0;

range = array[4] - array[0];

for (start = 1; start <= 10; start++) {

temp = array[start + 4] - array[start];

if (temp < range) {

range = temp;

keystart = start;

}

}

Notice the use of an intermedairy variable. This is so we don't perform the same calculation twice (array[start+4] - array[start]). From a programmer's point of view, it is more efficient to look up a value than it is to recalculate the same value.

As for the points, your question asks if there is a more elegant way in which to solve your problem. I have suggested the only possible change necessary to achieve a better solution. Please judge accordingly.

Agreed. But bare in mind that, with IL-compiled languages like C# you may end up with the same execution speed. If you would do it in assembly, you may find out that moving memory is more expensive than calculating, but assembly optimization, especially with modern processors who pipeline and predict the next action, it is extremely hard to come with a "best" or "most speedy" solution (that would be a chapter on its own). But the readability definitely increases.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Fast Find Duplicate AND SIMILAR strings Program | 5 | 107 | |

CAGR Calculation For SIP | 13 | 55 | |

Sampling | 3 | 35 | |

wordsWithoutList challenge | 24 | 58 |

how to add IIS SMTP to handle application/Scanner relays into office 365.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**14** Experts available now in Live!