 # unable to understand solution for ques: CHN08

My code gives the correct result but shows a “TLE” on submission in Codechef. So, I tried seeing the successful solutions in Java. However, I am unable to understand the logic here. (How it provides correct answer for n>3, just the switch case bit.)
I post the successful solution here. Please help me with it. As most successful solutions have this logic I am not posting the contributor’s name:

``````import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
int t,i,n,a,b,res;
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader buffer = new BufferedReader(in);
t = Integer.parseInt(buffer.readLine().trim());
int MOD = 1000000000 + 7;
String line;
while(t-->0)
{
res = 0;
line = buffer.readLine();
String myStr[] = line.trim().split("\\s+");
a = Integer.parseInt(myStr);
b = Integer.parseInt(myStr);
n = Integer.parseInt(myStr);
n = n-1;
n %= 6;
//System.out.println("n%6: "+n);
switch(n)
{
case 0:
res = a;
break;
case 1:
res = b;
break;
case 2:
res = b-a;
break;
case 3:
res = -a;
break;
case 4:
res = -b;
break;
case 5:
res = a-b;
break;
default:
break;
}
res = res%MOD;
if(res>=0)
System.out.println(res);
else
System.out.println(MOD+res);
}
}
}``````

Give some more thought to the question. Try to use pen-paper and manually find values of f(1) to f(13). You will see a nice pattern.

Just change the equation from `f(x) = f(x-1) + f(x+1).` to `f(x+1)=f(x)-f(x-1)`

1 Like

Its a periodic function. If i recall correctly, f(x+6)=f(x) is the property which holds here.

Had it not been there, then yes, matrix exp would be a general solution. Since OP asked about logic of the above code only, i didnt go much into matrix exp.