Halvor Strand

	public static int levenshteinDistance(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		for(int i = 0; i <= a.length(); i++)
			c[i][0] = i;

		for(int j = 0; j <= b.length(); j++)
			c[0][j] = j;

		for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                    if (a.charAt(i-1) == b.charAt(j-1))
                    	c[i][j] = c[i-1][j-1];
                    else
                    	c[i][j] = Math.min(c[i-1][j] + 1, Math.min(c[i][j-1] + 1, c[i-1][j-1] + 1));

		return c[a.length()][b.length()];
	}

Code

	// time: Ο(length(a)*length(b))
	// space: Θ(length(a)*length(b))
	public static int lcs(String a, String b)
	{
		int[][] c = new int[a.length()+1][b.length()+1];

		for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++)
                    if (a.charAt(i-1) == b.charAt(j-1))
                    	c[i][j] = c[i-1][j-1] + 1;
                    else
                    	c[i][j] = Math.max(c[i-1][j], c[i][j-1]);

		return c[a.length()][b.length()];
	}

Code

public static int gcd(int a, int b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

public static int lcm(int a, int b)
{
	return Math.abs(a*b)/gcd(a,b);
}

Code

public static boolean isPowerOfTwo(int x)
{
	return ((x & (x-1)) == 0);
}

Code

public static Vector<Integer> primeFactorize(int x)
{
	Vector<Integer> factors = new Vector<Integer>();

	for(int i = 2; i <= Math.sqrt(x); i++)
	{
		while(x%i == 0)
		{
			factors.add(i);
			x /= i;
		}
	}

	if(x > 1)
		factors.add(x);

	return factors;
}

Code

	public static boolean isPrime(int x)
	{
		if(x < 3)
			return (x == 2);

		for(int i = 3; i <= Math.sqrt(x); i++)
			if(x % i == 0)
				return false;

		return true;
	}

Code