We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Well you could do that, but you don't need to. I submitted a solution using dynamic programming, and one using just regular recursion. The difference in running time is so small that it prints the same running times, even though one runs in linear time and the other one in exponential time. They should increase the test size and limit the amount of running time so that without the use of dynamic programming you can't solve the problem imo.
static String fibonacciModified(int t1, int t2, int n) {
BigInteger c=new BigInteger("0");
BigInteger a=new BigInteger(t1+"");
BigInteger b=new BigInteger(t2+"");
for (int i=0;i
{
c=a.add(b.multiply(b));
a=b;
b=c;
}
return c.toString();
}**
I hope this will help you
publicclassSolution{publicstaticvoidmain(String[]args){/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */inti,n;BigIntegera,b;Scannersc=newScanner(System.in);a=sc.nextBigInteger();b=sc.nextBigInteger();n=sc.nextInt();BigInteger[]val=newBigInteger[n];val[0]=a;val[1]=b;for(i=2;i<n;i++){val[i]=(val[i-1].pow(2)).add(val[i-2]);}System.out.println(val[i-1]);}}
Solution.java:6: error: cannot find symbol
BigInteger a,b;
^
symbol: class BigInteger
location: class Solution
Solution.java:7: error: cannot find symbol
Scanner sc=new Scanner(System.in);
^
symbol: class Scanner
location: class Solution
Solution.java:7: error: cannot find symbol
Scanner sc=new Scanner(System.in);
^
symbol: class Scanner
location: class Solution
Solution.java:11: error: cannot find symbol
BigInteger [] val = new BigInteger[n];
^
symbol: class BigInteger
location: class Solution
Solution.java:11: error: cannot find symbol
BigInteger [] val = new BigInteger[n];
^
symbol: class BigInteger
location: class Solution
5 errors
I solved it with recursion. Probably stupid but the problem is defined recursively so it was the first thing that popped in my mind. If you memoize the recursive calls it needn´t be terribly inefficient.
The point of doing it in DP and not in recursion is that recursion takes a lot of time while DP doesnt. Doesnt make any sense doing it in recursion as it is said to do it in dp.
DP comes from Dynamic Programming, is an algorithm paradigm or a technique to solve complex problems breaking them into small ones. Just like you I still do not have any idea about what it is or how to implemented. If you find any DP course for dummies, please let me know, the ones I've found are a little bit difficult to follow.
You are calculating tn by solving the problem from t1 to tn, and recording the results in order to calculate the one you need.
That's the whole idea of dynamic programming: to solve a complex instance of a problem using the solution to smaller instances.
This problem is so simple that you can't really appreciate the technique. If you want an example of a more "serious" DP algorithm, you might look to a classic like the Wagner–Fischer algorithm to compute the distance between strings. It's simple enough but not trivial.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Fibonacci Modified
You are viewing a single comment's thread. Return to all comments →
Well you could do that, but you don't need to. I submitted a solution using dynamic programming, and one using just regular recursion. The difference in running time is so small that it prints the same running times, even though one runs in linear time and the other one in exponential time. They should increase the test size and limit the amount of running time so that without the use of dynamic programming you can't solve the problem imo.
This problem doesn't even need recursion.. a for loop can solve this problem too
Yes, BigInteger in for loop will solve it.
how u sloved big integer in for loop??can u explain?
Here is the snippet,
y is it necessary to add "" while initializing the constructor of biginteger ?
Because BigInteger doesn't take int in its constructor but can take a string .So adding "" makes a integer , string .
A nice way is to use valueOf() function of BigInteger class.
oh thank u
why not use:
directly?
my code was correct but how to use biginteger from your code i understands
thanks
Compile time error
Compile Message
Solution.java:6: error: cannot find symbol BigInteger a,b; ^ symbol: class BigInteger location: class Solution Solution.java:7: error: cannot find symbol Scanner sc=new Scanner(System.in); ^ symbol: class Scanner location: class Solution Solution.java:7: error: cannot find symbol Scanner sc=new Scanner(System.in); ^ symbol: class Scanner location: class Solution Solution.java:11: error: cannot find symbol BigInteger [] val = new BigInteger[n]; ^ symbol: class BigInteger location: class Solution Solution.java:11: error: cannot find symbol BigInteger [] val = new BigInteger[n]; ^ symbol: class BigInteger location: class Solution 5 errors
I solved it with recursion. Probably stupid but the problem is defined recursively so it was the first thing that popped in my mind. If you memoize the recursive calls it needn´t be terribly inefficient.
Can you post your recursive solution, please.
public static BigInteger fiboMod(BigInteger t1,BigInteger t2,int n){ n = n-1; if(n == 1){ return t2; } return fiboMod(t2,t2.pow(2).add(t1),n); }This is not DP. Its plain Recursion.
The point of doing it in DP and not in recursion is that recursion takes a lot of time while DP doesnt. Doesnt make any sense doing it in recursion as it is said to do it in dp.
Yes, but memoized recursion can give similar results to DP with only slight overhead (e.g. here).
recurssion with memoziation is same as iterative
I did it using a simple loop and I don't even know what DP is. Could you please show me what a solution using DP looks like?
DP comes from Dynamic Programming, is an algorithm paradigm or a technique to solve complex problems breaking them into small ones. Just like you I still do not have any idea about what it is or how to implemented. If you find any DP course for dummies, please let me know, the ones I've found are a little bit difficult to follow.
https://www.youtube.com/watch?v=P8Xa2BitN3I Check this video out, it might be helpful if you want to understand the basics of Dynamic programming.
Your solution is a DP solution.
You are calculating tn by solving the problem from t1 to tn, and recording the results in order to calculate the one you need.
That's the whole idea of dynamic programming: to solve a complex instance of a problem using the solution to smaller instances.
This problem is so simple that you can't really appreciate the technique. If you want an example of a more "serious" DP algorithm, you might look to a classic like the Wagner–Fischer algorithm to compute the distance between strings. It's simple enough but not trivial.