Sum of Squares with Worker Threads

Problem

Print the sum of the squares of all numbers. Compute each square as a separate task on worker threads (a thread pool in Java and Python). Collect the results and add them.

Constraints

  • 1 <= n <= 1000
  • |a[i]| <= 10^6

Examples

Input

4
1 2 3 4

Output

30

Solutions

AlternativeTime O(n)Space O(n)

Submitting a task returns at once with a Future. get() waits for the result. The pool must be shut down in a finally block. For tiny tasks like this one a plain loop is faster; threads pay off for slow work such as network calls.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : The sum of squares.
 * Approach: Worker threads.
 * 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 long solve(int[] a) {
        // Step 1: A fixed pool has 4 worker threads. Each task squares one number.
        java.util.concurrent.ExecutorService pool = java.util.concurrent.Executors.newFixedThreadPool(4);
        java.util.List<java.util.concurrent.Future<Long>> results = new java.util.ArrayList<>();

        try {
            // Step 2: submit gives a Future at once. The work runs in the background.
            for (int value : a) {
                final long number = value;
                results.add(pool.submit(() -> number * number));
            }

            // Step 3: get waits for each task and returns its result. We add the results.
            long total = 0;
            for (java.util.concurrent.Future<Long> result : results) {
                total += result.get();
            }
            return total;
        } catch (Exception error) {
            throw new RuntimeException(error);
        } finally {
            // Step 4: Always stop the pool. Otherwise the program may never end.
            pool.shutdown();
        }
    }

    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(solve(a));
    }
}
Hints (1)
  1. What does Future.get() do?