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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #230: Fibonacci Words
  4. Discussions

Project Euler #230: Fibonacci Words

Contest ends in
Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • lexus5000
    4 years ago+ 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);
    }
    
    12|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy