Stream.mapMulti: Repeat Each Number

Problem

Each number x (1 or bigger) of the array must appear x times in the result, next to each other, and the order of the numbers is kept. For [2, 1, 3] the result is 2 2 1 3 3 3. Print the result.

Constraints

  • 1 <= n <= 100
  • 1 <= value <= 20

Examples

Input

3
2 1 3

Output

2 2 1 3 3 3

Solutions

AlternativeTime O(sum)Space O(sum)

Two loops: the outer one goes over the numbers, the inner one writes the number x times. It works in every Java version.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Repeat each number.
 * Input   : n and the numbers.
 * Output  : The repeated numbers.
 * Approach: Nested loops
 * Time    : O(sum)
 * Space   : O(sum)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int[] solve(int[] a) {
        // Step 1: Count the output size, then fill the result array. Every number x is written x times.
        int total = 0;
        for (int value : a) {
            total += value;
        }
        int[] out = new int[total];
        int at = 0;
        for (int value : a) {
            for (int i = 0; i < value; i++) {
                out[at++] = value;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(Arrays.stream(solve(a)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Hints (1)
  1. How big is the result?