## Monday, 8 June 2015

### fibonacci series for all the number using string

The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by adding up the two numbers before it. Similarly, the 3 is found by adding the two numbers before it (1+2).
By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation $F_n = F_{n-1} + F_{n-2},\!\,$
with seed values $F_1 = 1,\; F_2 = 1$
or $F_0 = 0,\; F_1 = 1.$
Solution-
public int get FibonacciSeq(int n)
{
if(n<-1) return -1;
if(n==0) return 0;
if(n==1|| n==2) return 1;
int f0 = 0, f1 = 1;
int result = 0;
for (int k = 3; k <= n; k++) {
result = f0 + f1;
f0 = f1;
f1 = result;
}
return result;
}
But the problem with above approach is there is range of n. Hence the number and the result should be in Integer range otherwise it will return -ive value. To solve this problem we can use below approach which takes input as integer and return String as a result.
public static String FibonacciSeq(int n) {
if (n < 0)
return "Not a valid Input";
if (n == 0)
return "0";
if (n == 1 || n == 2)
return "1";
String f0 = "0";
String f1 = "1";
int k = 3;
String out = "";
while (k <= n) {
out = "";
int carry = 0;
int c = 0;
int i = f0.length() - 1, j = f1.length() - 1;
for (; i >= 0 || j >= 0; i--, j--) {
if (i >= 0 && j >= 0) {
c = f0.charAt(i) - '0' + f1.charAt(j) - '0' + carry;
} else if (i >= 0) {
c = f0.charAt(i) - '0' + carry;
} else if (j >= 0) {
c = f1.charAt(j) - '0' + carry;
}
out = (Integer.toString(c % 10)) + out;
carry = c / 10;
}
if (carry != 0) {
out = Integer.toString(carry) + out;
}
f0 = f1;
f1 = out;
k++;
}
return out;
}