Project Euler - Problem 25

euler.java

package euler;

import java.math.BigInteger;
import java.util.HashMap;

public class Fib {
	private static HashMap<BigInteger, BigInteger> map = new HashMap<>();
	public static void main(String[] args) {
		for (int i = 1; i < Integer.MAX_VALUE; i++) {
			if (f(BigInteger.valueOf(i)).toString().length() == 1000) {
				System.out.println(i);
				break;
			}
		}
	}
	
	public static BigInteger f(BigInteger n) {
		if (map.containsKey(n)) return map.get(n);
		if (n.equals(BigInteger.ONE)) return BigInteger.ONE;
		else if (n.equals(BigInteger.valueOf(2))) return BigInteger.ONE;
		else {
			BigInteger i = f(n.subtract(BigInteger.ONE)).add(f(n.subtract(BigInteger.valueOf(2))));
			map.put(n, i);
			return i;
		}
	}
}