Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Missing numbers from sorted list

Ranch Hand
Posts: 61
Which collections object is good to show the missing number from a sorted list. Any ideas please!!!
Suppose my numbers are
100234
100235
100237
100238
Then the output should be 100246
[ February 16, 2004: Message edited by: divya madala ]

Tom Blough
Ranch Hand
Posts: 263
Look at the abstract Map class. A HashMap would probably work fine for your application.
Tom Blough
[ February 16, 2004: Message edited by: Tom Blough ]

Angel Dobbs-Sciortino
Ranch Hand
Posts: 101
If you use a TreeSet of Integer objects, it will sort the numbers for you. Then you can use an Iterator to step through the Set, and subtract the current number from the previous number to find out if it skipped a number or not.
Angel
[ February 16, 2004: Message edited by: Angel Dobbs-Sciortino ]

Nils Hofmann
Greenhorn
Posts: 9
hi,
it's a bit circuitous, but you can try the following. set up a second list (called newList)
with all possible numbers. when you call newList.removeAll(oldList) then in newList remain
only that numbers, which are not in oldList.
example:

nils
[ February 17, 2004: Message edited by: Nils Hofmann ]

Thomas Paul
mister krabs
Ranch Hand
Posts: 13974
it's a bit circuitous, but you can try the following. set up a second list (called newList) with all possible numbers.
Wouldn't that be a very big list? In fact, wouldn't it be an infinitely big list?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Wouldn't that be a very big list? In fact, wouldn't it be an infinitely big list?
True. But since the list has already been sorted it's easy to find the smallest and largest number in the list; you can restrict things that way.
Even so, it seems a bit unnecessary to list all numbers in the range first. I'd just loop through the sorted list, comparing each element to the previous element. If the difference is greater than 1, you've got some missing numbers and ought to be able to determine what they are. Add them to the list of missing numbers, and continue looping through the original list.
Note that in this strategy, you will have to be a little careful at the beginning and end of the list, to make sure you don't accidentally refer to elements that don't exist. You may have to adjust the initial and exit conditions of the loop; they're not quite what you're used to seeing.