-


FIBONACCI....Series
Let's see an interesting example of Fibonacci series by solving this interesting problem.






Last digit of Fibonacci series after performing K task


You are given a number N and a number K you have to print the last digit of the Fibonacci series after recursively generating the set of S such that
S ={Fk,F2*k…….} i.e the set S should only contain the Kth index Fibonacci number.
Kindly see the explanation for better understanding
Explanation:
consider : N=10 and K=3;
The Fibonacci series is:
0 1 1 2 3 5 8 13 21 34         //1 based indexing
since K=3
S={1,5,21}
S={21}
There fore the output is 1     //The last digit of that number
Examples: The First number is N and then K.
Input :10 3 
Output :1
see the explanation part.

Approach
1.Brute Force
We can generate the Fibonacci series and store in the array and then apply nested loop
to search for the last K Fibonacci number and then print the last digit.
Problems The basic problem while following the above approach is that we
can't store the Fibonacci number of even 100 in long long int also.
100 = 354224848179261915075 So it will be very much difficult to follow the above approach. 


2.Using Mathematical Approach
1.Here we don't require the number we only require the last digit of the number
2.We don't have to store all the Fibonacci series we just have to find the last number
which will be left in the last set S.
Now our problem require only 1 thing that is find the index of the last number which will remain in the S
To do that we can take the help of Arithmetic Progression 
Example 
N=10 K=3
Fibonacci Series=0 1 1 2 3 5 8 13 21 34
so here a (initial term)=K (the index)
n (total element)=N/3;
d (difference)= a;
tn (last element)=a+(n-1)*d=3+(3-1)*3 = 9
so the last element number which will be in our set is Fibonacci number at index (9-1) i.e 8 (since 1 based indexing)
we have to do this thing until we have less than or equal to K element in our set.
Now after finding the index number we have to find the last digit of that number.
See this post to find the last digit of the Fibonacci number in O(1).




#include<bits/stdc++.h>
using namespace std;
// Finds nth fibonacci number
long long int fib(long long int f[], long long int  n)
{
        // 0th and 1st number of
        // the series are 0 and 1
    f[0] = 0;
    f[1] = 1;
        // Add the previous 2 numbers 
        // in the series and store 
        // last digit of result
    for (long long int i = 2; i <= n; i++)
        f[i] = (f[i - 1] + f[i - 2]) % 10;
    return f[n];
}
// Returns last digit of n'th Fibonacci Number
int findLastDigit(int n)
{
    long long  f[60] = {0};
   
    // Precomputing units digit of  
    // first 60 Fibonacci numbers
     fib(f, 60);
   
    return f[n % 60];
}
//To find the last element in the set
long long int A_P(long long int n,long long int K)
{     
       long long int ans,tn,d,a;
       while(n>K)
        {
            a=a*K;
            d=a;
            n=n/K;
            tn=a+(n-1)*d;
            ans=tn;
            
        }
       return ans;
}
// Driver code
int main()
{
    long long int N,K,last_element,answer;
    N=10,K=3;
         
     //if N==1 then 0
     if(N==1)
        {
            cout<<0<<endl;
        }
     //if N==2 then 1
      else if(N==2)
        {
            cout<<1<<endl;
        }
     //Else find the last element
        
       else{
        last_element=A_P(N,K);
        answer=findLastDigit(last_element-1);
        cout<< answer <<endl;
         
        }
     
    return 0;
}




Time Complexity:O(n)


If you are finding any thing wrong or inappropriate kindly write to us.
Please follow the blog for more such updates...



Comments

Post a Comment

Popular posts from this blog

-
Image
Sphenic Number A  Sphenic Number  is a positive integer  n  which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather the first 3 digits after 1 are prime or not. Eg. 30 (sphenic number) 30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30) the set of divisor is (1,2,3,5,6,10,15,30) Examples: 30 = 2 × 3 × 5 Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather...
Read more

Fibonacci numbers with help of DP

-
Image
Well...the most and simple program which every programmer may have solved at least once.... Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.... with base condition f(0)=0  f(1)=1 In general: f(n)=f(n-1) +f(n-2) Basic Approach: A simple method that is a direct recursive implementation mathematical recurrence relation given above Here is simple CPP program.... #include<bits/stdc++.h> using namespace std;     int fib( int n) {      if (n <= 1)          return n;      return fib(n-1) + fib(n-2); }     int main () {      int n = 9;      cout << fib(n);      return 0; } That was simple....isn't it........
Read more
-
Image
Tutorial-2 is out!!!!! Fasten your seat-belt! Problem-2:- Understanding this problem and its solution properly will make a strong foundation for you in the DP world .(This worked for me :-) ) Here we go- Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:- Sum of those elements is maximum(Sum of the subset is maximum) . No 2 elements in the subset should be consecutive. Example :- {2,4,6,7,8} Answer:- {2+6+8=16} Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array. For the above example, dp[1] = 2 (2), [This is the best answer you could get if size of the array was one] dp[2]= 4(4),[This is the best answer you could get if size of the array was two] dp[3]=8(6+2),[This is the best answer you could get if size of the array was three]………lets call this equation-(1)… dp[4]=11(7+4),[This is the best answer you could get if size of ...
Read more