Make minimum int value by combining unique values from int array using Java Stream API

Question

I need to implement a method int minValue(int[] values) using the Stream API. The method takes an array of ints from 0 to 9, takes unique values, and returns a minimum possible number combined of these unique digits. The array must not be converted to a string.

Example #1: input {1,2,3,3,2,3}, returned value - 123;

Example #2: input {9,8}, returned value – 89.

I don’t know how to implement the multiplication of every stream member to the sequence of values using Stream API: if my sorted stream has values (5, 3, 1) I need to perform 5 * 1 + 3 * 10 + 1 * 100. How can I do this using Stream API?

My solution with a simple for loop is below:

    private static int minValue(int[] values) {
        int result = 0;
        int capacity = 1;

        int[] ints = Arrays.stream(values)
            .boxed()
            .distinct()
            .sorted(Collections.reverseOrder())
            .mapToInt(Integer::intValue).toArray();

        for (int i = 0; i < ints.length; i++) {
            result = result + ints[i] * capacity;
            capacity = capacity * 10;
        }

        return result;
    }

Nikolas Charalambidis · Accepted Answer · 2021-06-23T04:58:38.417

Calling distinct, sort, and reduce respectively is a way to go:

int result = Arrays.stream(values)
            .distinct()                   // unique digits
            .sorted()                     // sorted digits (descending)
            .reduce((l, r) -> l * 10 + r) // shifts a digit and adds another one
            .orElseThrow();               // this is up to you

The reduce part might look tricky, let's inspect it step-by-step on the 1234 number sequence (already distinct and sorted).

l=1 and r=2 -> l * 10 + r gives 10 + 2 = 12 (new l).
l=12 and r=3 -> l * 10 + r gives 120 + 3 = 123 (new l)
l=123 and r=4 -> l * 10 + r gives 1230 + 4 = 1234 (finish)

Edit: As Holger pointed out, this would work only in the sequential processing. The following solution would work in parallel:

String result = Arrays.stream(values)
            .distinct()
            .sorted()
            .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)
            .toString();
int intResult = Integer.parseInt(result);

@VishwaRatna: It is simple. Distinct digits from `111` is `1` hence it will be also the output. — Nikolas Charalambidis, Jun 21 '21 at 10:29
Happens to work in sequential execution with the current implementation, but is formally wrong due to its non-associative reduction function. Never try with a parallel stream. The Stream API’s `reduce` is not a left-fold. — Holger, Jun 21 '21 at 13:20

Holger · Answer 2 · 2021-06-21T13:26:27.800

This kind of repeated calculation can be converted into a formally correct stream operation, as has been demonstrated in How to compute the hash code for a stream in the same way as List.hashCode()

The difference between these tasks only lies in the factor, you need factor ten, the other needed 31.

But the solution is not simple. You could write a simple but formally wrong reduction operation with a non-associative function which still works in sequential execution with the current implementation, but that would be an abuse of the Stream API and begs the question what you hope to gain from using the Stream API.

The Stream API does not always lead to a simple or efficient solution. That especially applies to your initial task of identifying all distinct digits of a very small set and getting them in an ordered intermediate result.

You can implement the whole operation as

private static int minValue(int[] values) {
    int allDigits = 0;
    for(int i: values) allDigits |= 1 << i;

    int result = 0;
    for(int digit = 1; digit < 10; digit++)
        if((allDigits & (1 << digit)) != 0) result = result * 10 + digit;

    return result;
}

Since the task description states that all values are in the 0..9 range, they easily fit into a single int value which has 32 bits. When we set the 0th to 9th bit when encountering that digit, we have the information in an intrinsically sorted way. The second loop just probes each digit’s bit and when the digit is present, it performs a result = result * 10 + digit; calculation similar to the linked Q&A which works when iterating from smallest to largest digit, but iterating from largest to smallest similar to your approach would work too:

private static int minValue(int[] values) {
    int allDigits = 0;
    for(int i: values) allDigits |= 1 << i;

    int result = 0;
    for(int digit = 9, factor = 1; digit > 0; digit--)
        if((allDigits & (1 << digit)) != 0) {
            result = result + digit * factor;
            factor *= 10;
        }

    return result;
}

score 0 · Answer 3 · answered Jun 21 '21 at 10:09

0

Here is a way to do it:

    final int[] result = {0};
    Arrays.stream(values).boxed().distinct().sorted()
            .mapToInt(Integer::intValue).forEach(i -> result[0] = i + result[0] * 10);
    return result[0];

answered Jun 21 '21 at 10:09

Roophie

141
8

Make minimum int value by combining unique values from int array using Java Stream API

3 Answers3