Solved

# Finding the 5 closest numbers from a larger array a numbers

Posted on 2009-02-23
333 Views
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;

``````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;

}

}
``````
0
Question by:dban00b

LVL 10

Expert Comment

this is a complexaty n algorithm. So it is the fastest
0

LVL 84

Expert Comment

if array accesses are the slowest operation, you may be able to cut them by as much as half by  caching them or noting that any inteval smaller than 5 that has a range larger than the smallest range seen so far, cannot be contained in an interval of 5 that has a smaller range, but the added complexity may be more likely to slow down the search if the tine for array accesses is is the same as the time for, say a comparison operation.
0

LVL 39

Expert Comment

I've given it some though and came to the conclusion that this is a typical O(n) problem. Same as, for instance, Max/Min on an unordered array.

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).
0

LVL 39

Expert Comment

Sorry for doubling the answers, the question didn't refresh well...
0

LVL 16

Expert Comment

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-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.

0

LVL 16

Expert Comment

Reposted due to error...

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.
0

LVL 20

Expert Comment

If the cost is in the reading from array[] (but not from internal data; e.g. the array might be on a tape or it might in fact be a complicated function call), the following looks up each entry only once.

``````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

}
``````
0

LVL 16

Expert Comment

thehangman

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'?
0

LVL 1

Author Comment

Okay it seems I really can't do any better.  It's just one of those things that any more-complicated solution is simply going to make it worse.

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.
0

LVL 10

Expert Comment

you give the points to the one giving the easer explanation.

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

LVL 16

Accepted Solution

dban00b

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.
0

LVL 39

Expert Comment

> From a programmer's point of view, it is more efficient to look up a value than it is to recalculate the same value.

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.
0

LVL 16

Expert Comment

dban00b

Thank you for accepting my solution.
0

## Featured Post

### Suggested Solutions

Fast Find Duplicate AND SIMILAR strings Program 5 107
CAGR Calculation For SIP 13 55
Sampling 3 35
wordsWithoutList  challenge 24 58
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
how to add IIS SMTP to handle application/Scanner relays into office 365.
In this sixth video of the Xpdf series, we discuss and demonstrate the PDFtoPNG utility, which converts a multi-page PDF file to separate color, grayscale, or monochrome PNG files, creating one PNG file for each page in the PDF. It does this via a c…