How to get frequency count of integers in a stream? (perhaps using Collectors)

[Anil Philip]

The Lonely Integer Challenge on HackerRank is here.

Given an array of integers, where all elements but one occur twice, find the unique element.


I solved this problem in a simple way using a Set,
but I was wondering if there is a way to get frequency count of integers in a stream? (perhaps using Collectors.groupingBy()?).
I looked at the docs but could not figure out how to do it using streams and Collectors.

Note that my code is in lonelyinteger(). The rest is the framework provided by HackerRank.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'lonelyinteger' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static int lonelyinteger(List<Integer> iList) {
    // Write your code here
        Set<Integer> loners = new HashSet<>();
        iList.forEach(i->{
            if(loners.contains(i))
                loners.remove(i); // it has been paired
             else
                loners.add(i); // potentially alone
            });
        // assumes at least one element.
        return loners.stream().findFirst().get();
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.lonelyinteger(a);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

[Carey Brown]

There's a neat little trick using XOR that will solve this efficiently. If you XOR the same numbers (i.e. a pair) together you get zero. You can go through the list XORing each integer in turn and all pairs will cancel each other out regardless of where the occur leaving the result being the one lonely integer.

[Anil Philip]

Carey Brown wrote:There's a neat little trick using XOR that will solve this efficiently. If you XOR the same numbers (i.e. a pair) together you get zero. You can go through the list XORing each integer in turn and all pairs will cancel each other out regardless of where the occur leaving the result being the one lonely integer.

And what if they are not side by side?

[Carey Brown]

"regardless of where the occur"

[Anil Philip]

Carey Brown wrote:"regardless of where the occur"

ok, I missed that

[Mike Simmons]

The XOR trick is cool and super fast, but only really works for this very specific problem. What if there were two elements that only occur once?  

I do think it's pretty useful to know how to get a frequency count of items in an array, collection, or stream.  Collectors.groupingBy() is definitely useful - but not a complete solution itself.  The standard library does provide several other methods you can combine for a fairly concise solution:

  public static <E> Map<E, Long> frequencyMapOf(Collection<E> collection) {
    return collection.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
  }

[Anil Philip]

Mike Simmons wrote:The XOR trick is cool and super fast, but only really works for this very specific problem. What if there were two elements that only occur once?  

Great point!
I thought the same problem will be with the Set solution I posted above, but I am unable to get it to fail on input like

6
3 1 3 1 2 3
OR
6
2 3 1 3 1 3
OR
6
3 1 3 1 3 2

I expect it to return 3 (incorrect value) but it returns 2 (correct value).

Mike Simmons wrote:
I do think it's pretty useful to know how to get a frequency count of items in an array, collection, or stream.  Collectors.groupingBy() is definitely useful - but not a complete solution itself.  The standard library does provide several other methods you can combine for a fairly concise solution:

  public static <E> Map<E, Long> frequencyMapOf(Collection<E> collection) {
    return collection.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
  }

I am trying to understand

Collectors.groupingBy(Function.identity(), Collectors.counting())

Does the classifier Function.identity() work only because the elements are Integers with only one attribute (their value)
- if they were objects with other attributes then we would have to supply the method Foo::getAttribute ?

Trying to step through it in the IDE, This is really formidable code!

    Collector<T, ?, M> groupingBy(Function<? super T, ? extends K> classifier,
                                  Supplier<M> mapFactory,
                                  Collector<? super T, A, D> downstream) {
        Supplier<A> downstreamSupplier = downstream.supplier();
        BiConsumer<A, ? super T> downstreamAccumulator = downstream.accumulator();
        BiConsumer<Map<K, A>, T> accumulator = (m, t) -> {
            K key = Objects.requireNonNull(classifier.apply(t), "element cannot be mapped to a null key");
            A container = m.computeIfAbsent(key, k -> downstreamSupplier.get());
            downstreamAccumulator.accept(container, t);
        };
        BinaryOperator<Map<K, A>> merger = Collectors.<K, A, Map<K, A>>mapMerger(downstream.combiner());
        @SuppressWarnings("unchecked")
        Supplier<Map<K, A>> mangledFactory = (Supplier<Map<K, A>>) mapFactory;

        if (downstream.characteristics().contains(Collector.Characteristics.IDENTITY_FINISH)) {
            return new CollectorImpl<>(mangledFactory, accumulator, merger, CH_ID);
        }
        else {
            @SuppressWarnings("unchecked")
            Function<A, A> downstreamFinisher = (Function<A, A>) downstream.finisher();
            Function<Map<K, A>, M> finisher = intermediate -> {
                intermediate.replaceAll((k, v) -> downstreamFinisher.apply(v));
                @SuppressWarnings("unchecked")
                M castResult = (M) intermediate;
                return castResult;
            };
            return new CollectorImpl<>(mangledFactory, accumulator, merger, finisher, CH_NOID);
        }
    }

[Stephan van Hulst]

Anil Philip wrote:Does the classifier Function.identity() work only because the elements are Integers with only one attribute (their value)
- if they were objects with other attributes then we would have to supply the method Foo::getAttribute ?

No.

The classifier is simply a function that converts an element of the stream to another value. That value can be (and usually is) a property of the element being converted, but it can also be something completely different.

Sometimes you don't want to convert the value, but just use the value itself. You can do it with a lambda expression:

element -> element

Or you can do it with the identity() operator.

This is not limited to value types either. You can do this with any reference type.

[Mike Simmons]

Stephan's answer is 100% correct.  I would add: it works based on what we want to used as the key for grouping the elements.  In this case, we were using the elements themselves for grouping.  But yes, in many cases if you had an object with attributes, you would probably want to use something like Foo::getAttribute.  If you don't do that, then the grouping is done based on how equals() and hashCode() are done in whatever class you're using.  That's true in our case above too - for Integer, equals() and hashCode() have already been overridden to provide simple, sensible results that allow two different Integer instances with equal values to evaluate as equal.