Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a numerical range and a list of used numbers that fall within that range I need to compress the range into blocks of used and unused numbers.

For example:

range: 0 to 10
used:  3,4,5,9

I need an output like

0-2: free
3-5: used
6-8: free
9:   used
10:  free

Not sure where to start with this, so any guidance appreciated.

share|improve this question
Have you written any code or pseudocode yet? Please post what you have tried. – default.kramer Jan 9 '13 at 17:27
Is the list of used numbers ordered? – vaughandroid Jan 9 '13 at 17:27
this is very similar to run length encoding ... – jk. Jan 9 '13 at 17:28
up vote 2 down vote accepted

As I commented, this is very similar to run length encoding, in fact if used is sorted it is arguably a bit easier!

With run length encoding you would start with the first number in an array and scan forward counting the number between each transition between used/unused (or in your case recording the start and end index which is essentially equivalent).

However if used is sorted you already know where the first transition from unused->used is so you can start there and scan used for the next transition from used->unused, you then also know the next unused->used transition as its the next used number.

if used isn't sorted you could either sort it first (likely a good idea if used is small compared to range) or you could use range and used to first construct a full array of used and unused numbers e.g. 00011100010 and run length encode this.

share|improve this answer
I've sorted this in a simple way by just scanning the the whole range and checking if every number is in used. as the size of range and used is small this is inexpensive. Thanks – Chris Blackwell Jan 11 '13 at 15:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.