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...
Posts
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); } ...
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 ...
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...