Project Euler #230: Fibonacci Words

  • + 4 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:

    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);
    }