Find missing integer in a sequential sorted stream

Question

Let's say I have a list

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));

How do I find "N4", I mean, how I find that the missing integer is 4?

What I've tried so far

Integer missingID = arr.stream().map(p -> Integer.parseInt(p.substring(1))).sorted()
                .reduce((p1, p2) -> (p2 - p1) > 1 ? p1 + 1 : 0).get();

This doesn't work because reduce is not intended to work in the way I need in this situation, actually, I have no idea how do that. If there's no missing number, than the next must be "N6" - or just 6 - (in this example)

It must be done with java standard stream's library, no use of third parties.

Answer 1

The algorithm to implement here is based from this one: to find the missing number in a sequence of integers, the trick is to:

• calculate the sum of the elements in the sequence.
• calculate the sum of the elements the sequence would have with the missing number: this is easy to do since we can determine the minimum, the maximum and we know that the sum from a sequence of integer going from min to max is max*(max+1)/2 - (min-1)*min/2.
• find the difference between those two sums: that's our missing number

In this case, we can collect statistics on our Stream by first mapping to an IntStream formed by only the numbers themselves and then calling summaryStatistics(). This returns a IntSummaryStatistics that has all the values we want: min, max and sum:

public static void main(String[] args) {
    List<String> arr = Arrays.asList("N3", "N7", "N4", "N5", "N2");
    IntSummaryStatistics statistics = 
        arr.stream()
           .mapToInt(s -> Integer.parseInt(s.substring(1)))
           .summaryStatistics();

    long max = statistics.getMax();
    long min = statistics.getMin();

    long missing = max*(max+1)/2 - (min-1)*min/2 - statistics.getSum();
    System.out.println(missing); // prints "6" here
}

If there is no missing number, this will print 0.

Answer 2

Here's the solution involving the pairMap operation from my free StreamEx library. It prints all the missing elements of the sorted input:

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));
StreamEx.of(arr).map(n -> Integer.parseInt(n.substring(1)))
                .pairMap((a, b) -> IntStream.range(a+1, b))
                .flatMapToInt(Function.identity())
                .forEach(System.out::println);

The pairMap operation allows you to map every adjacent pair of the stream to something else. Here we map them to the streams of the skipped numbers, then flatten these streams.

The same solution is possible without third-party library, but looks more verbose:

ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));
IntStream.range(0, arr.size()-1)
                .flatMap(idx -> IntStream.range(
                    Integer.parseInt(arr.get(idx).substring(1))+1,
                    Integer.parseInt(arr.get(idx+1).substring(1))))
                .forEach(System.out::println);