Posts

-
Image
                                                    Hard Fibonacii...... Today we eill learn to find the n'th fibonacci number after %M. Since it is vey dfficult to store the large Fibonacci number,because the rate is exponention. But there is a unique properties of Fibonacci series by which it is periodic n nature.... Lets see an samll example  m = 2 or m = 3. Take a detailed look at this table. Do you see? Both these sequences are periodic!  For m = 2, the period is 011 and has length 3, while for  m = 3 the period is 01120221 and has length 8.  Therefore, to compute, say, F2015 mod 3 we just need to find the remainder of 2015 when divided by 8. Since 2015 = 251·8 + 7, we conclude that F2015 mod 3 = F7 mod 3 = 1. This is true in general: for any integer m ≥ 2, the sequence Fn mod m is periodic. The period always...
Post a Comment
Read more
-
Extended Euclid Algorithm: This is the extended form of Euclid’s Algorithm explained in previous post. GCD(A,B) has a special property that it can always be represented in the form of an equation, i.e., Ax + By = GCD(A, B). This algorithm gives us the coefficients (x and y) of this equation which will be later useful in finding the Modular Multiplicative Inverse. These coefficients can be zero or negative in their value. This algorithm takes two inputs as A and B and returns GCD(A, B) and coefficients of the  equations as output. Implementation: #include < iostream > int d, x, y; void extendedEuclid(int A, int B) { if(B == 0) { d = A; x = 1; y = 0; } else { extendedEuclid(B, A%B); int temp = x; x = y; y = temp - (A/B)*y; } } int main( ) { extendedEuclid(16, 10); cout << ”The GCD of 16 and 10 is ” << d << endl; cout << ”Coefficient x...
Post a Comment
Read more
-
Greatest Common Divisor Greatest Common Divisor (GCD) of two or more numbers is the largest positive number that divides all the numbers which are being taken into consideration. For example: GCD of 6, 10 is 2 since 2 is the largest positive number that divides both 6 and 10. Naive Approach: We can traverse over all the numbers from min(A, B) to 1 and check if the current number divides both A and B or not. If it does, then it will be the GCD of A and B. int GCD(int A, int B) { int m = min(A, B), gcd; for(int i = m; i > 0; --i) if(A % i == 0 && B % i == 0) { gcd = i; return gcd; } } Time Complexity: Time complexity of this function is O(min(A, B)). Euclid’s Algorithm: Idea behind Euclid’s Algorithm is GCD(A, B) = GCD(B, A % B). The algorithm will recurse until A % B = 0. int GCD(int A, int B) { if(B==0) return A; else return GCD(B, A % B); } ...
Post a Comment
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 ...
Post a Comment
Read more
-
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  ={F k ,F 2*k …….} i.e the set  S  should only contain the  K th  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...
Post a Comment
Read more