Test title

test content

view plainprint?

1.   

Fibonacci numbers

Mathematica
Note, that this implementation exists. Algorithm is:

Fibonacci[n_] := Round[GoldenRatio^n/Sqrt[5]]

Be aware, that this formula:

can not be trivially applied in other languages.

Java
In Java, we have arbitrarily large integers and decimals, but prebuilt classes lack the functionality (it's a shame). For example we can not easily take root of 5. To do this, we would need to use a library like JScience or write Newton approximation method (what can be quite error prone process).

	/**
	* Gives the Fibonacci number.
	*
	* @param n
	* element to return.
	* @return Fibonacci and Negafibonacci numbers.
	*/
	public static BigInteger fibonacci(final int n) {
	if (n == 0)
	return BigInteger.ZERO;
	int an = Math.abs(n);
	BigInteger[] result = { BigInteger.ONE, BigInteger.ONE };
	BigInteger[] tmp = new BigInteger[2];
	for (int i = 1; i < an; i++) {
	tmp[0] = result[0].add(result[1]);
	tmp[1] = result[0];
	result = Arrays.copyOf(tmp, tmp.length);
	}
	return ((n < 0) && (n % 2 == 0)) ? result[1].negate() : result[1];
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#
In C#, there is no arbitrarily large decimals. It does have class decimal (with 28-29 significant digits), but assuming that Math class supports it, is just asking too much (it's a shame). But thumbs up, for it at least has BigInteger.

	/// <summary>
	/// Gives the Fibonacci number.
	/// </summary>
	/// <remarks>using System.Numerics;</remarks>
	/// <param name="n">element to return.</param>
	/// <returns>Fibonacci and Negafibonacci numbers.</returns>
	public static BigInteger fibonacci(int n)
	{
	if (n == 0)
	return BigInteger.Zero;
	int an = Math.Abs(n);
	int nr = 2;
	BigInteger[] result = { BigInteger.One, BigInteger.One };
	BigInteger[] tmp = new BigInteger[nr];
	for (int i = 1; i < an; i++)
	{
	tmp[0] = BigInteger.Add(result[0], result[1]);
	tmp[1] = result[0];
	Array.Copy(tmp, 0, result, 0, 2);
	}
	return ((n < 0) && (n % 2 == 0)) ? -result[1] : result[1];
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Binary search

Java
In java, Collections/Arrays class contains binary search.

view plainprint?

1. Collections.binarySearch(list, key);  
2. Arrays.binarySearch(array, key);  

Collections.binarySearch(list, key);
Arrays.binarySearch(array, key);

My naive generic implementation is recursive and ignores the fact, that I should use ListIterator for data structures, that do not have random access (ex. LinkedList).

	/**
	* Function returns location of unique item in a sorted list.
	*
	* @param <T> Class, that implements comparable interface.
	* @param data list of elements
	* @param searchValue element to search for
	* @return Location of the the element. If item is not found, -1 is returned.
	* @throws java.lang.NullPointerException
	* If any checked element in the list is 'null'.
	*/
	public static <T extends Comparable<? super T>> //
	int binarySearch(final List<T> data, T searchValue)
	throws java.lang.NullPointerException {
	return binarySearch(data, searchValue, 0, data.size() - 1);
	}
	/**
	* Function returns location of unique item in a sorted list.
	*
	* @param <T> Class, that implements comparable interface.
	* @param data list of elements
	* @param searchValue element to search for
	* @param left lower bound
	* @param right upper bound
	* @return Location of the the element. If item is not found, -1 is returned.
	* @throws java.lang.NullPointerException
	* If any checked element in the list is 'null'.
	*/
	public static <T extends Comparable<? super T>> //
	int binarySearch(final List<T> data, T searchValue, int left, int right)
	throws java.lang.NullPointerException {
	final int NOT_FOUND = -1;
	if (right < left)
	return NOT_FOUND;
	int mid = (left + right) >>> 1;
	int cmp = searchValue.compareTo(data.get(mid));
	if (cmp > 0)
	return binarySearch(data, searchValue, mid + 1, right);
	if (cmp < 0)
	return binarySearch(data, searchValue, left, mid - 1);
	return mid;
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#
In C#, list itself and Arrays class contains binary search.

list.BinarySearch(key);
Array.BinarySearch(array, key);

My naive Java implementation translated to C#.

	/// <summary>
	/// Function returns location of unique item in a sorted list.
	/// </summary>
	/// <typeparam name="T">Class, that implements comparable interface.</typeparam>
	/// <param name="data">list of elements</param>
	/// <param name="searchValue">element to search for</param>
	/// <returns>Location of the the element. If item is not found, -1 is returned.</returns>
	/// <exception cref="System.NullReferenceException">
	/// If any checked element in the list is 'null'. (Other then first one)
	/// </exception>
	public static int binarySearch<T>(IList<T> data, T searchValue)
	where T : IComparable<T>
	{
	return binarySearch(data, searchValue, 0, data.Count());
	}
	/// <summary>
	/// Function returns location of unique item in a sorted list.
	/// </summary>
	/// <typeparam name="T">Class, that implements comparable interface.</typeparam>
	/// <param name="data">list of elements</param>
	/// <param name="searchValue">element to search for</param>
	/// <param name="left">lower bound</param>
	/// <param name="right">upper bound</param>
	/// <returns>Location of the the element. If item is not found, -1 is returned.</returns>
	/// <exception cref="System.NullReferenceException">
	/// If any checked element in the list is 'null'. (Other then first one)
	/// </exception>
	public static int binarySearch<T>(IList<T> data, T searchValue, int left, int right)
	where T : IComparable<T>
	{
	const int NOT_FOUND = -1;
	if (right < left)
	return NOT_FOUND;
	int mid = (int)((uint)(left + right) >> 1);
	int cmp = searchValue.CompareTo(data[mid]);
	if (cmp > 0)
	return binarySearch(data, searchValue, mid + 1, right);
	if (cmp < 0)
	return binarySearch(data, searchValue, left, mid - 1);
	return mid;
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Mathematica
In mathematica, Combinatorica library contains binary search.

BinarySearch[list, key]

Merge sort

Will take O(n * log (n)) time, and does not depend on input.

Java

	/**
	* Method sorts a list ascendingly using merge sort algorithm.
	*
	* @param <T>
	* Non null class, that implements comparable interface.
	* @param data
	* List of T type elements, to be sorted ascendingly.
	* @throws java.lang.NullPointerException
	* If any element in the list is 'null'.
	* @throws java.lang.UnsupportedOperationException
	* If list is unmodifiable or immutable.
	*/
	public static <T extends Comparable<? super T>> //
	void mergeSort(final List<T> data) {
	mergeSort(data, 0, data.size() - 1);
	}
	/**
	* Method sorts a part of list ascendingly using merge sort algorithm.
	*
	* @param <T>
	* Non null class, that implements comparable interface.
	* @param data
	* List of T type elements, to be sorted ascendingly.
	* @throws java.lang.NullPointerException
	* If any element in the list is 'null'.
	* @throws java.lang.UnsupportedOperationException
	* If list is unmodifiable or immutable.
	*/
	public static <T extends Comparable<? super T>> //
	void mergeSort(final List<T> data, int lowBound, int highBound) {
	if (lowBound >= highBound)
	return;
	// partition
	int maxLowBound = (lowBound + highBound) / 2;
	int minHighBound = maxLowBound + 1;
	mergeSort(data, lowBound, maxLowBound);
	mergeSort(data, minHighBound, highBound);
	// merge
	boolean comp;
	Queue<T> storageLow = new LinkedList<T>();
	Queue<T> storageHigh = new LinkedList<T>();
	for (int i = lowBound; i <= maxLowBound; i++)
	storageLow.add(data.get(i));
	for (int i = minHighBound; i <= highBound; i++)
	storageHigh.add(data.get(i));
	while ((storageLow.size() > 0) && ((storageHigh.size() > 0))) {
	comp = storageLow.peek().compareTo(storageHigh.peek()) < 0;
	data.set(lowBound++, comp ? storageLow.poll() : storageHigh.poll());
	}
	while (storageLow.size() > 0)
	data.set(lowBound++, storageLow.poll());
	while (storageHigh.size() > 0)
	data.set(lowBound++, storageHigh.poll());
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#

	/// <summary>
	/// Method sorts a list ascendingly using merge sort algorithm.
	/// </summary>
	/// <typeparam name="T"> Non null class, that implements comparable interface.
	/// </typeparam>
	/// <param name="data">List of T type elements, to be sorted ascendingly.</param>
	/// <exception cref="System.NullReferenceException">
	/// If any element in the list is 'null'. (Other then first one)
	/// </exception>
	/// <exception cref="System.NotSupportedException">
	/// If list is readonly.
	/// </exception>
	public static void mergeSort<T>(IList<T> data) where T : IComparable<T>
	{
	mergeSort(data, 0, data.Count - 1);
	}
	/// <summary>
	/// Method sorts a part of list ascendingly using merge sort algorithm.
	/// </summary>
	/// <typeparam name="T"> Non null class, that implements comparable interface.
	/// </typeparam>
	/// <param name="data">List of T type elements, to be sorted ascendingly.</param>
	/// <exception cref="System.NullReferenceException">
	/// If any element in the list is 'null'. (Other then first one)
	/// </exception>
	/// <exception cref="System.NotSupportedException">
	/// If list is readonly.
	/// </exception>
	public static void mergeSort<T>(IList<T> data, int lowBound, int highBound)
	where T : IComparable<T>
	{
	if (lowBound >= highBound)
	return;
	// partition
	int maxLowBound = (lowBound + highBound) / 2;
	int minHighBound = maxLowBound + 1;
	mergeSort(data, lowBound, maxLowBound);
	mergeSort(data, minHighBound, highBound);
	// merge
	bool comp;
	Queue<T> storageLow = new Queue<T>();
	Queue<T> storageHigh = new Queue<T>();
	for (int i = lowBound; i <= maxLowBound; i++)
	storageLow.Enqueue(data[i]);
	for (int i = minHighBound; i <= highBound; i++)
	storageHigh.Enqueue(data[i]);
	while ((storageLow.Count() > 0) && ((storageHigh.Count() > 0)))
	{
	comp = storageLow.Peek().CompareTo(storageHigh.Peek()) < 0;
	data[lowBound++] = comp ? storageLow.Dequeue() : storageHigh.Dequeue();
	}
	while (storageLow.Count() > 0)
	data[lowBound++] = storageLow.Dequeue();
	while (storageHigh.Count() > 0)
	data[lowBound++] = storageHigh.Dequeue();
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Insertion sort

Efficient for small lists, with size less then 30.

Special cases are:

• if list is almost sorted, it will be near linear time
• if sorted list is reversed, it will be quadratic time

Java

	/**
	* Method sorts a list ascendingly using insertion sort algorithm.
	*
	* @param <T>
	* Non null class, that implements comparable interface.
	* @param data
	* List of T type elements, to be sorted ascendingly.
	* @throws java.lang.NullPointerException
	* If any element in the list is 'null'.
	* @throws java.lang.UnsupportedOperationException
	* If list is unmodifiable or immutable.
	*/
	public static <T extends Comparable<? super T>> //
	void insertionSort(final List<T> data)
	throws java.lang.NullPointerException,
	java.lang.UnsupportedOperationException {
	int i, j;
	for (i = 1; i < data.size(); i++) {
	T temp = data.get(i);
	j = i;
	while ((j > 0) && (temp.compareTo(data.get(j - 1)) < 0)) {
	data.set(j, data.get(j - 1));
	j--;
	}
	data.set(j, temp);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#

	/// <summary>
	/// Method sorts a list ascendingly using insertion sort algorithm.
	/// </summary>
	/// <typeparam name="T"> Non null class, that implements comparable interface.
	/// </typeparam>
	/// <param name="data">List of T type elements, to be sorted ascendingly.</param>
	/// <exception cref="System.NullReferenceException">
	/// If any element in the list is 'null'. (Other then first one)
	/// </exception>
	/// <exception cref="System.NotSupportedException">
	/// If list is readonly.
	/// </exception>
	public static void insertionSort<T>(IList<T> data) where T : IComparable<T>
	{
	int i, j;
	for (i = 1; i < data.Count; i++)
	{
	T temp = data[i];
	j = i;
	while ((j > 0) && (temp.CompareTo(data[j - 1]) < 0))
	{
	data[j] = data[j - 1];
	j--;
	}
	data[j] = temp;
	}
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Euler Problem 49 solution

Time (s): ~0.002

view plainprint?

1. package margusmartseppcode.From_40_to_49;  
2.   
3. import java.util.Arrays;  
4.   
5. public class Problem_49 {  
6.   
7.  // Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0))  
8.  static boolean isPrimeS(final int n) {  
9.   final int r = (int) Math.floor(Math.sqrt(n));  
10.   for (int f = 5; f <= r; f += 6)  
11.    if (n % f == 0 || n % (f + 2) == 0)  
12.     return false;  
13.   return true;  
14.  }  
15.   
16.  static boolean isPerm(char[] a, char[] b) {  
17.   if (a.length != b.length)  
18.    return false;  
19.   Arrays.sort(a);  
20.   Arrays.sort(b);  
21.   return Arrays.equals(a, b);  
22.  }  
23.   
24.  static boolean arePerms(int... n) {  
25.   if (n.length == 0)  
26.    return true;  
27.   for (int i = 1; i < n.length; i++)  
28.    if (!isPerm(("" + n[i - 1]).toCharArray(), ("" + n[i])  
29.      .toCharArray()))  
30.     return false;  
31.   return true;  
32.  }  
33.   
34.  static boolean arePrimes(int... n) {  
35.   for (int i : n)  
36.    if (!isPrimeS(i))  
37.     return false;  
38.   
39.   return true;  
40.  }  
41.   
42.  public static void main(String[] args) {  
43.   int a, b, c;  
44.   a = b = c = 0;  
45.   
46.   for (a = 1489;; a += 2) {  
47.    if (a % 3 == 0 || a % 5 == 0 || a % 7 == 0)  
48.     continue;  
49.      
50.    b = a + 3330;  
51.    c = a + 6660;  
52.   
53.    if (arePrimes(a, b, c))  
54.     if (arePerms(a, b, c))  
55.      break;  
56.   }  
57.   System.out.println("" + a + b + c);  
58.  }  
59. }  

package margusmartseppcode.From_40_to_49;

import java.util.Arrays;

public class Problem_49 {

 // Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0))
 static boolean isPrimeS(final int n) {
  final int r = (int) Math.floor(Math.sqrt(n));
  for (int f = 5; f <= r; f += 6)
   if (n % f == 0 || n % (f + 2) == 0)
    return false;
  return true;
 }

 static boolean isPerm(char[] a, char[] b) {
  if (a.length != b.length)
   return false;
  Arrays.sort(a);
  Arrays.sort(b);
  return Arrays.equals(a, b);
 }

 static boolean arePerms(int... n) {
  if (n.length == 0)
   return true;
  for (int i = 1; i < n.length; i++)
   if (!isPerm(("" + n[i - 1]).toCharArray(), ("" + n[i])
     .toCharArray()))
    return false;
  return true;
 }

 static boolean arePrimes(int... n) {
  for (int i : n)
   if (!isPrimeS(i))
    return false;

  return true;
 }

 public static void main(String[] args) {
  int a, b, c;
  a = b = c = 0;

  for (a = 1489;; a += 2) {
   if (a % 3 == 0 || a % 5 == 0 || a % 7 == 0)
    continue;
   
   b = a + 3330;
   c = a + 6660;

   if (arePrimes(a, b, c))
    if (arePerms(a, b, c))
     break;
  }
  System.out.println("" + a + b + c);
 }
}

Euler Problem 48 solution

Time (s): ~0.034

view plainprint?

1. package margusmartseppcode.From_40_to_49;  
2.   
3. public class Problem_48 {  
4.  public static void main(String[] args) {  
5.   long result = 0, d10 = 10000000000L;  
6.   for (long u = 1, tmp = u; u <= 1000; result += tmp, ++u, tmp = u)  
7.    for (long v = 1; v < u; ++v)  
8.     tmp = (tmp * u) % d10;  
9.   
10.   System.out.println(result % d10);  
11.  }  
12. }  

package margusmartseppcode.From_40_to_49;

public class Problem_48 {
 public static void main(String[] args) {
  long result = 0, d10 = 10000000000L;
  for (long u = 1, tmp = u; u <= 1000; result += tmp, ++u, tmp = u)
   for (long v = 1; v < u; ++v)
    tmp = (tmp * u) % d10;

  System.out.println(result % d10);
 }
}

Time (s): ~0.224

view plainprint?

1. package margusmartseppcode.From_40_to_49;  
2.   
3. import java.math.BigInteger;  
4.   
5. public class Problem_48 {  
6.  // Note: i = 2 !!!  
7.  public static void main(String[] args) {  
8.   BigInteger num = BigInteger.ONE;  
9.   for (int i = 2; i < 1000; i++)  
10.    num = num.add(BigInteger.valueOf(i).pow(i));  
11.   String result = num.toString();  
12.   System.out.println(result.substring(result.length() - 10));  
13.  }  
14. }  

package margusmartseppcode.From_40_to_49;

import java.math.BigInteger;

public class Problem_48 {
 // Note: i = 2 !!!
 public static void main(String[] args) {
  BigInteger num = BigInteger.ONE;
  for (int i = 2; i < 1000; i++)
   num = num.add(BigInteger.valueOf(i).pow(i));
  String result = num.toString();
  System.out.println(result.substring(result.length() - 10));
 }
}