Fold Left and Fold Right

Problem

Reduce the array with subtraction in two ways. Fold left: ((a0 - a1) - a2) - ... Fold right: a0 - (a1 - (a2 - ... - a(n-1))). Print left=X on the first line and right=Y on the second line. (Subtraction is not associative, so the two answers can differ.)

Constraints

  • 1 <= n <= 1000

Examples

Input

3
10 3 2

Output

left=5
right=9

Solutions

Best approachTime O(n)Space O(n)

A fold combines a list into one value with a function. Fold left starts from the first number and fold right from the last. With a non-associative function like minus, the direction changes the answer.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Fold two ways.
 * Input   : n and the numbers.
 * Output  : Two lines.
 * Approach: reduce and reduceRight
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a) {
        // Step 1: Fold left: reduce takes the numbers from the left and combines the result so far with the next number.
        long left = java.util.Arrays.stream(a).asLongStream().reduce((x, y) -> x - y).getAsLong();
        // Step 2: Fold right: walk from the right. The new number is on the left side of the minus sign.
        long[] backwards = new long[a.length];
        for (int i = 0; i < a.length; i++) {
            backwards[i] = a[a.length - 1 - i];
        }
        long right = java.util.Arrays.stream(backwards).reduce((acc, x) -> x - acc).getAsLong();
        return new String[] {"left=" + left, "right=" + right};
    }

    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(String.join("\n", solve(a)));
    }
}
Hints (2)
  1. Which number is the start value of fold right?
  2. Why do the answers differ?