How could we get an unique element from a double array, using a map‽

Question

I am currently solving the following programming exercise: Find the unique number The statement is:

There is an array with some numbers. All numbers are equal except for one. Try to find it!

Kata.findUniq(new double[]{ 1, 1, 1, 2, 1, 1 }); // => 2 Kata.findUniq(new double[]{ 0, 0, 0.55, 0, 0 }); // => 0.55

It’s guaranteed that array contains more than 3 numbers.

The tests contain some very huge arrays, so think about performance.

First my thought was to get all elements frequencies as a map, and then return the key which frequency value is just 1.

I wrote the following:

import java.util.stream.*;

 public class Kata {
    public static double findUniq(double arr[]) {

      Map<Double, Long> frequencies = Arrays.stream(arr)
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

      System.out.println("Map: "+map);

    }
}

So it outputs:

./src/main/java/Kata.java:8: error: method collect in interface DoubleStream cannot be applied to given types;
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));
        ^
  required: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>
  found: Collector<Object,CAP#1,Map<Object,Long>>
  reason: cannot infer type-variable(s) R
    (actual and formal argument lists differ in length)
  where R is a type-variable:
    R extends Object declared in method <R>collect(Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>)
  where CAP#1 is a fresh type-variable:
    CAP#1 extends Object from capture of ?
./src/main/java/Kata.java:10: error: cannot find symbol
      System.out.println("Map: "+map);
                                 ^
  symbol:   variable map
  location: class Kata
2 errors

I suppose the way to solve this issue is to understand:

required: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R>
  found: Collector<Object,CAP#1,Map<Object,Long>>

I do know it expects: Supplier<R>,ObjDoubleConsumer<R>,BiConsumer<R,R> and I am writting: Collector<Object,CAP#1,Map<Object,Long>> but what does it mean? How could we fix it? Why is it generated?

Then I tried a second approach: use a HashSet to get all distinct doubles, then remove the one which is not unique, and return the unique one, which is stored in the HashSet.

import java.util.*;
import java.util.stream.*;

 public class Kata {
    public static double findUniq(double arr[]) {
      System.out.println("\nOriginal array: "+Arrays.toString(arr));

      Set<Double> unique = new HashSet<Double>();
      double repeated = Double.MIN_VALUE;

      for(int i = 0; i < arr.length; i++){
        if(repeated != arr[i] && !unique.add(arr[i])){
          repeated = arr[i];
        }
      }
      unique.remove(repeated);
      System.out.println("Set: "+Arrays.toString(unique.toArray()));
      return (double)unique.toArray()[0];
    }
}

My question is, how could we achieve to return the unique element, using the first approach, counting frequencies with a map and then returning the key which value is 1‽.

I have also read:

Java Hashmap: How to get key from value? How to get unique items from an array?

Answer 1

The compiler error occurs because the Collector that you are using does not work on DoubleStream - the specialised Stream type for primitive doubles. What you can do is to turn the DoubleStream into a Stream<Double> first, then apply the Collector:

Map<Double, Long> frequencies = Arrays.stream(arr)
        .boxed() // this is the key method to call
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

Then you need to find the KVP with value 1, but maps aren't really meant for this though:

System.out.println("Map: "+ 
    frequencies.entrySet().stream()
        .filter(x -> x.getValue() == 1)
        .findFirst().get().getKey());

Note that there are much faster solutions than this. Keep in mind that exactly one double is different!