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
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.
/*
* 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)
- Which number is the start value of fold right?
- Why do the answers differ?