We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
We don't need to build string, just set up the string length counter to get the first on bigger than the Number n. Then decompose the F(n)= F(n-1) + F(n-2). This structure indicate the string is always prefix with F(n-1). If number is bigger then F(n-1), then decompose the F(n-2), otherwise decompose F(n-1). This is my Java Version which pass all test:
static int getResult(String one, String two, BigInteger n) {
List<BigInteger> fcount = new ArrayList<BigInteger>();
BigInteger oneInt = BigInteger.valueOf(one.length());
BigInteger twoInt = BigInteger.valueOf(two.length());
fcount.add(oneInt);
fcount.add(twoInt);
int result = -1;
do{
fcount.add(oneInt.add(twoInt));
oneInt = twoInt;
twoInt = fcount.get(fcount.size()-1);
}while(twoInt.compareTo(n)<0);
int i = fcount.size() -3;
int currentIndex = i;
while(i>=0) {
BigInteger current = fcount.get(i);
if(n.compareTo(current)>0) {
n = n.subtract(current);
i--;
currentIndex = i;
}
else
{
if(i==0)
result = one.charAt(n.intValue() - 1);
if(i==1)
result = two.charAt(n.intValue() - 1);
i = currentIndex - 2;
currentIndex = i;
}
}
if(result == -1)
result = two.charAt(n.intValue() - 1);
return (result - 48);
}
Project Euler #230: Fibonacci Words
You are viewing a single comment's thread. Return to all comments →
We don't need to build string, just set up the string length counter to get the first on bigger than the Number n. Then decompose the F(n)= F(n-1) + F(n-2). This structure indicate the string is always prefix with F(n-1). If number is bigger then F(n-1), then decompose the F(n-2), otherwise decompose F(n-1). This is my Java Version which pass all test: