MathUtils.java

package manu.sandbox.utils;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.*;

public class MathUtils {

    public static boolean isPrime(int n) {
        if (n == 2 || n == 3) {
            return true;
        } else if (n < 2 || n % 2 == 0 || n % 3 == 0 || !((n + 1) % 6 == 0 || (n - 1) % 6 == 0)) {
            return false;
        } else {
            for (int i = 6; (i - 1) * (i - 1) <= n; i += 6) {
                if (n % (i - 1) == 0 || n % (i + 1) == 0) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * Calculate count of prime numbers in range [min, max] - both inclusive
     *
     * @param min minimum of the range
     * @param max maximum number of the range
     */
    public static int countOfPrimesBetween(int min, int max) {
        int countPrimes = 0;
        for (int i = min; i <= max; i++) {
            if (isPrime(i)) {
                countPrimes++;
            }
        }
        return countPrimes;
    }

    // Old way
    private static class PrimesCountFinder1 extends Thread {
        private final int min, max;
        private int returnVal;

        public PrimesCountFinder1(int min, int max) {
            this.min = min;
            this.max = max;
        }

        public void run() {
            this.returnVal = countOfPrimesBetween(this.min, this.max);
        }

        public int returnVal() {
            return this.returnVal;
        }
    }

    // New way
    private static class PrimesCountFinder2 implements Callable<Integer> {
        private final int min, max;

        public PrimesCountFinder2(int min, int max) {
            this.min = min;
            this.max = max;
        }

        @Override
        public Integer call() throws Exception {
            return countOfPrimesBetween(this.min, this.max);
        }
    }


    /**
     * Calculate count of prime numbers in range [min, max] - both inclusive
     *
     * @param min        minimum of the range
     * @param max        maximum number of the range
     * @param numThreads Number of threads to run in parallel while calculating
     */
    public static int countOfPrimesBetweenV1(int min, int max, int numThreads) throws InterruptedException {
        int countPrimes = 0;
        List<PrimesCountFinder1> l = new ArrayList<>();
        for (int i = 0; i < numThreads; i++) {
            PrimesCountFinder1 p = new PrimesCountFinder1(min + ((max - min) * i) / numThreads,
                    min - 1 + ((max + 1 - min) * (i + 1)) / numThreads);
            p.start();
            l.add(p);
        }
        for (int i = 0; i < numThreads; i++) {
            PrimesCountFinder1 p = l.get(i);
            p.join();
            countPrimes += p.returnVal();
        }
        return countPrimes;
    }


    public static int countOfPrimesBetweenV2(int min, int max, int numThreads) throws ExecutionException, InterruptedException {
        int countPrimes = 0;
        ExecutorService executor = Executors.newFixedThreadPool(numThreads);
        List<Callable<Integer>> callableList = new ArrayList<>();
        for (int i = 0; i < numThreads; i++) {
            callableList.add(new PrimesCountFinder2(min + ((max - min) * i) / numThreads,
                    min - 1 + ((max + 1 - min) * (i + 1)) / numThreads));
        }
        final List<Future<Integer>> futureList = executor.invokeAll(callableList);
        for (int i = 0; i < numThreads; i++) {
            countPrimes += futureList.get(i).get();
        }
        return countPrimes;
    }

    public static int sumOfDigits(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Argument cannot be negative");
        }
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }


    public static Map<Integer, Integer> factorise(int n) {
        Map<Integer, Integer> factors = new HashMap<>();
        for (int i = 2; i <= n; i++) {
            if (!isPrime(i))
                continue;
            int r = n, f = 0;
            while (r % i == 0) {
                r = r / i;
                f++;
            }
            if (f == 0) continue;
            factors.put(i, f);
        }
        return factors;
    }

    /**
     * Method to compute number of possible ways of selecting items from a collection, <b>irrespective of the order</b><br>
     * <br>
     * <b>Note:</b> This method is accurate only up to 15 digits
     *
     * @param n Number of elements in the collection
     * @param r Number of elements to be chosen
     * @return Number of possible combinations
     */
    public static long nCrApprox(int n, int r) {
        validateNR(n, r);
        if (n == r) {
            return 1;
        } else {
            if (r > n / 2) {
                r = n - r;
            }
            if (r == 1) {
                return n;
            }
            double result = n % 2 == 0 && r % 2 == 1 ? 2.0 : 1.0;
            while (r > 0) {
                int numerator = n--, denominator = r--;
                if (numerator % 2 == 0) {
                    numerator /= 2;
                }
                if (denominator % 2 == 0) {
                    denominator /= 2;
                }
                result = (result * numerator) / denominator;
            }
            return Math.round(result);
        }
    }


    public static BigInteger factorial(int n) {
        BigInteger f = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }

    /**
     * Method to compute number of possible ways of selecting items from a collection, <b>irrespective of the order</b><br>
     * <br>
     * <b>Note:</b> This method is accurate only up to 15 digits
     *
     * @param n Number of elements in the collection
     * @param r Number of elements to be chosen
     * @return Number of possible combinations
     */
    public static BigInteger nCrPrecise(int n, int r) {
        validateNR(n, r);
        return factorial(n).divide(factorial(n - r).multiply(factorial(r)));
    }

    private static void validateNR(int n, int r) {
        if (n < 0 || r < 0) {
            throw new IllegalArgumentException("Invalid input: Both n and r are expected to be positive");
        } else if (n < r) {
            throw new IllegalArgumentException("Invalid input: n should be greater than or equal to r");
        }
    }

    /**
     * Method to compute number of possible ways of selecting items from a collection
     *
     * @param n Number of elements in the collection
     * @param r Number of elements to be chosen
     * @return Number of possible combinations
     */
    public static BigInteger nPr(int n, int r) {
        validateNR(n, r);
        BigInteger p = BigInteger.ONE;
        for (int i = 0; i < r; i++) {
            p = p.multiply(BigInteger.valueOf(n - i));
        }
        return p;

    }

    public static BigDecimal pVisa(int cap, int totalApplicants, int myApplications) {
        return BigDecimal.ONE.subtract(
                new BigDecimal(nPr(totalApplicants - myApplications, cap))
                        .divide(
                                new BigDecimal(nPr(totalApplicants, cap)
                                ), 18, BigDecimal.ROUND_HALF_EVEN)
        );
    }

}