# 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) {
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;
}
}
}
```

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`.

Source: stackoverflow