What should be the optimal way of solving Recurrence relation for really Huge number greater than Integer maximum value

Question

I want to find the Nth number of the Recurrence Equation

T(n)=T(n-1)+3T(n-2)+3T(n-3)+(n-4),T(1)=T(4)=1,T(2)=T(3)=3

so if suppose you entered 2,5,9 as input, output should be T(2)=3,T(5)=20,T(9)=695

what I did is create an array of size equal to maximum of all input value and storing solution of T(i) at index i.Then look up into the array for specific index. eg array[3] for T(3),array[5] for T(5),etc

The code worked fine till maximum number is not greater than maximum integer value system can hold i.e

Integer.MAXValue.

Because the index of array can only be integer then if number is n=1855656959555656 what should be the best way to find the solution of T(1855656959555656)? as clearly I cant create an array of size=1855656959555656..

I have even tried BigInteger from java.Math but with no success. I have to find some other approach.please suggest some ideas..

Thanks

Answer 1

you do not need to store every T(i), you only need to store 3 values T(i-1), T(i-2), T(i-3). While looping over i, check if the current i should be part of your output, if so put it out immediately or save it to an "output"-array.

edit: this part is quite inefficient. You check in every iteation EVERY needed output.

        for (int k = 0; k < arr.length; ++k) {
            if (count == arr[k])
                T[k] = temp[i];
            else if (arr[k] == 1)
                T[k] = 1;
            else if (arr[k] == 2)
                T[k] = 3;
            else if (arr[k] == 3)
                T[k] = 3;
            else if (arr[k] == 4)
                T[k] = 1;
        }

so your code runs in time (max*arr.length) you can reduce it to only (max). Use a HashMap with key=neededPosition (=count) value=position in arr

Init the map like this:

 Map<Long, Integer> map = new HashMap<Long, Integer>();
 for (int i = 0; i < arr.length; i++) {
        map.put(arr[i], i);
    }

if (map.containsKey(count)) {
    T[map.get(count)] = temp[i]
}

check the values 1-4 just once after the whole thing!

Answer 2

Not possible. The array size can be a maximum of Integer.MAX_VALUE (minus something usually 5 or 8, depending on the JVM capabilities). Why?. The index for an Array should be an integer thats a limitation.