Skip to content

Instantly share code, notes, and snippets.

@m-manu
Last active July 4, 2018 10:35
Show Gist options
  • Save m-manu/4987945e37c7394db7bfc48151eb33e8 to your computer and use it in GitHub Desktop.
Save m-manu/4987945e37c7394db7bfc48151eb33e8 to your computer and use it in GitHub Desktop.
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)
);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment