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

Answer 3

If there's only ONE missing number in the array, and if all numbers are positive, you could use the XOR algorithm, as explained in this question and its answers:

List<String> list = Arrays.asList("N5", "N2", "N3", "N6");
int xorArray = list.stream()
        .mapToInt(p -> Integer.parseInt(p.substring(1)))
        .reduce(0, (p1, p2) -> p1 ^ p2);
int xorAll = IntStream.rangeClosed(2, 6)
        .reduce(0, (p1, p2) -> p1 ^ p2);
System.out.println(xorArray ^ xorAll); // 4

The advantage of this approach is that you don't need to use extra data structures, all you need is a couple of ints.

---

EDIT as per @Holger's comments below:

This solution requires you to know the range of the numbers in advance. Although on the other hand, it doesn't require the list and stream to be sorted.

Even if the list wasn't sorted, you could still get min and max (hence, the range) with IntSummaryStatistics, but this would require an extra iteration.

Answer 4

You could create a state object which is used to transform a single input stream into multiple streams of missing entries. These missing entry streams can then be flat mapped to produce a single output:

public class GapCheck {
    private String last;

    public GapCheck(String first) {
        last = first;
    }

    public Stream<String> streamMissing(String next) {
        final int n = Integer.parseInt(next.replaceAll("N", ""));
        final int l = Integer.parseInt(last.replaceAll("N", ""));
        last = next;
        return IntStream.range(l + 1, n).mapToObj(Integer::toString);
    }
} 

Usage:

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

arr.stream()
   .flatMap(new GapCheck(arr.get(0))::streamMissing)
   .forEach(System.out::println);

output:

2
4

Answer 5

This is more work than you might expect, but it can be done with a collect call.

public class Main {
    public static void main(String[] args) {
        ArrayList<String> arr = new ArrayList<String>(Arrays.asList("N1", "N2", "N3", "N5", "N7", "N14"));

        Stream<Integer> st = arr.stream().map(p -> Integer.parseInt(p.substring(1))).sorted();
        Holder<Integer> holder = st.collect(() -> new Holder<Integer>(), 
                (h, i) -> {
                    Integer last = h.getProcessed().isEmpty() ? null : h.getProcessed().get(h.getProcessed().size() - 1);
                    if (last != null) {
                        while (i - last > 1) {
                            h.getMissing().add(++last);
                        }
                    }
                    h.getProcessed().add(i);
                }, 
                (h, h2) -> {});
        holder.getMissing().forEach(System.out::println);
    }

    private static class Holder<T> {
        private ArrayList<T> processed;
        private ArrayList<T> missing;

        public Holder() {
            this.processed = new ArrayList<>();
            this.missing = new ArrayList<>();
        }

        public ArrayList<T> getProcessed() {
            return this.processed;
        }

        public ArrayList<T> getMissing() {
            return this.missing;
        }
    }
}

This prints

4
6
8
9
10
11
12
13

Note that this sort of thing isn't really a particularly strong fit for Streams. All of the stream processing methods will tend to pass you each item exactly one time, so you need to handle all runs of missing numbers at once, and in the end, you're writing kind of a lot of code to avoid just writing a loop.

Answer 6

Here is one solution using pure streams, albeit not very efficient.

public void test() {
    List<String> arr = new ArrayList(
                    Arrays.asList("N1", "N2", "N3", "N5", "N7"));

    List<Integer> list = IntStream
                .range(1, arr.size())
                .mapToObj(t -> new AbstractMap.SimpleEntry<Integer, Integer>(
                        extract(arr, t), extract(arr, t) - extract(arr, t - 1)))
                .filter(t -> t.getValue() > 1)
                .map(t -> t.getKey() - 1)
                .collect(Collectors.toList());

    System.out.println(list);
}

private int extract(List<String> arr, int t) {
    return Integer.parseInt(arr.get(t).substring(1));
}

Major performance block will be because of repeated parsing of list elements. However, this solution will be able to provide all missing numbers.