My code link:
TLE in test cases
Hi Dhiraj
This problem requires some precomputation. If you look closely you will find that there’s some kind of pattern being formed with the testcases… some kind of series. Look closely.
Note down the answers for different values of n from 1 to 10 , that should be enough. Just take a look and try to form a pattern. You will be able to catch it faster than you realise. After that precompute the answers for that series upto 45 (use long long int datatype or it won’t work) in an array , say A.
Then run the loop for testcases and simply output the value at A[n] for each input of n.
Once you are done with this question , try to think of the reason why this particular pattern was occuring here. Let me know if you need help with that.
I understand this reply might not seem much helpful but just take the look at the testcases … the answer’s right in front of you.
is it a fibonacii sequence?
Hi Dhiraj.
Yes , you are right.
Now just store the answers for this series using a loop (don’t use recursion or your time complexity would remain the same) and precompute the answers till 45. Store them in an array of long long int type.
Simply output the array elements when you run the loop for testcases.
its not the updated code , its the changed code , i was only doing mistake in the wrong output types just because it was mentioned in the question properly , you could have changed the part of code , and why that 45 just because you know the hidden testcases?
Its actally not a good way of helping
@tarunluthra
…please
Hi Dhiraj,
45 is not a random number. And no , I do not have any access to any testcases. I have just as much access as you . If you take a look at the constraints mentioned in the question , it is given that n can take any value between 1 and 44 , I chose 45 as it is the integer just after 44 . That was the only reason.
I also changed your data type to long long int as I have mentioned you to use the long long int data type in the above msg’s twice before . Fibonacci series grows extremely fast and goes out of the range of int very quickly. So to be on the safer side , it is better to use long long int to store its values.
Oh sorry I did not see the constraints for that , my bad
Backtracking is not an easy topic and takes a bit of time to grasp. Just go with the online videos and note down Prateek Bhaiya’s codes. Even just typing them while copying every word from my notebook helped me. At first even I couldn’t . Take it step by step.
Take the N Queen Problem for example. Copy down Prateek Bhaiya’s code. Now try some debugging. Change your code to print the matrix at every step. That will help you understand and grasp the inner working . Do the same with my Funky Chessboard code and so on.
Understanding its working at every step will give you the insight and help you learn better.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
@tarunluthra Hi. The if we insert n the answer should be (n+2) fibbonacci number, but why have you used the n+1th fib number in your code?