Thread-Safe Counter

Problem

Several threads increase the same counter. Read the number of threads t and the number of increments c for each thread. Print the final counter value. The correct result is t * c, so no update may be lost.

Constraints

  • 1 <= t <= 32
  • 0 <= c <= 10^5

Examples

Input

4 1000

Output

4000

Solutions

Best approachTime O(t * c)Space O(t)

counter++ is three steps: read, add, write. Two threads can read the same value and both write value + 1, so one update is lost. AtomicLong (Java) or a lock (Python) makes the update safe.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count with many threads.
 * Input   : Threads t and increments c.
 * Output  : The final counter.
 * Approach: Make each increment atomic.
 * Time    : O(t * c)
 * Space   : O(t)
 * 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(long a, long b) {
        // Step 1: AtomicLong makes each increment one single step that other threads can not interrupt.
        // A normal long with counter++ is three steps (read, add, write), and threads can lose updates.
        java.util.concurrent.atomic.AtomicLong counter = new java.util.concurrent.atomic.AtomicLong();
        Thread[] workers = new Thread[(int) a];

        // Step 2: Start t threads. Each one increments the counter c times.
        for (int w = 0; w < workers.length; w++) {
            workers[w] = new Thread(() -> {
                for (long i = 0; i < b; i++) {
                    counter.incrementAndGet();
                }
            });
            workers[w].start();
        }

        // Step 3: Wait for all threads.
        for (Thread worker : workers) {
            try {
                worker.join();
            } catch (InterruptedException error) {
                Thread.currentThread().interrupt();
            }
        }
        return counter.get();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. Why can counter++ lose an update?
  2. Which Java class gives atomic increments?