find nth word of a fibonacci word sequence (Java)

I’m trying to solve this assignment:

Let x[0] =0; x[1] =1; x[i] = x[i-2] + x[i-1]

Find the kth char of the word x[n] to see if it’s ‘0’ or ‘1’, with bound of 1 <= k < n <= 93

For example, with the sequence 0110110101101 we have

x[0] = 0

x[1] = 1

x[2] = 01

x[3] = 101

x[4] = 01101

x[5] = 10101101

When I test with n = 44 and higher, the IDE throws a OutOfMemoryError java heap space. I understand that the way I’m doing would store the nth word, the n-1th word, and the n-2th word of the sequence and that would occupy a lot of memory but I can’t figure out a better way.

After some draft work on papers I also see that to find the nth word after n = 3, the while loop only need to run n-2 times but no luck implementing

I also tried to store each word in a String ArrayList and do it with recursive but it’s even less efficient

Any tip is appreciated

Here is my code

import java.util.Scanner;
public class BinarySequence {
    public static void main(String[] args) {
        Scanner read = new Scanner(System.in);
        int t = read.nextInt(); //number of test to run
        while (t>0){
            String s0 = "0";
            String s1 = "1";
            int n = read.nextInt(); //nth fibonacci word
            int k = read.nextInt(); // kth char of the word
            System.out.println(fib(s0,s1,n-1).charAt(k-1));
            t--;
        }
    }
    private static String fib(String s0,String s1, int n) {
        String ans ="";
        if(n==0)
            return s0;
        else if(n==1)
            return s1;
        else {
            while(n>=0){
                ans = s0+s1;
                s0=s1;
                s1=ans;
                n--;
            }
            return ans;
        }
    }
}

Answer

The input k is limited to be between 1 and 92, so for calculating the sequence string you only need the first 92 characters. However, the start of the string is changing for each different x[i] value. For the first eleven¹ x[i] values the string depends on the full value of x[i-1] and x[i-2], but after/at the eleventh x[i] value the first string of x[i-2] is already long enough that the value of x[i-1] doesn’t matter anymore, as it is concatenated at the end of the result. The value of x[i-1] and x[i-2] for bigger indices can be shown as this:

x[i-1] = 1111111...1111111 + xxxxxxxxxx
x[i-2] = 2222222...2222222 + yyyyyyyyyy
x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx

Assume that the 111...111/222...222 parts (these are not the actual characters of course) are 92 characters long, then you don’t need the remaining stuff xxxxx... and yyyyy... after that anymore, as you cannot reach them with the limited k value anyway. So for your problem, the sequence of

x[i] = 2222222...2222222 + yyyyyyyyyy + 1111111...1111111 + xxxxxxxxxx

is the same as

x[i] = 2222222...2222222

for high enough i.

The remaining problem is now to calculate/select which sequence of 111..111 or 222...222 should be used when you calculate something like x[24] or even x[80]. Most likely it is something like an odd/even check where you write something like: “When n is even, use x[10], otherwise use x[11].”.

¹) Check for any off-by-one errors, the threshold of 92 characters might not be at index 11.