0import java.util.Scanner;
//0,1,1,2,3,5,8,13,21,34...
//fun(n)=fun(n-1)+fun(n-2) where n>=2
/*fib(9)=fib(8)+fib(7)
=fib(7)+fib(6)+fib(6)+fib(5)
=fib(6)+fib(5)+fib(5)+fib(4)+fib(5)+fib(4)+fib(4)+fib(3)
*/
public class FibonacciNumberFast {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long fno=fibonacciNumber(n);
System.out.println(fno);
}
public static long fibonacciNumber(int n){
int array[]= new int[n+1];
array[0]=0;
if(n==0)
return array[0];
array[1]=1;
for(int i=2;i<=n;i++)
array[i]=array[i-1]+array[i-2];
return array[n];
}
}
Algorithm 2– Finding GCD of a number
1) GCD using Recursion
2) GCD using naïve approach
import java.util.Scanner;
// Largest number which divides both a and b
public class GCDNaive {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
//long gcd = gcd(a, b);
//System.out.println("Result from GCD Naive "+gcd);
gcdFast(a, b);
}
static void gcdFast(long a, long b) {
if (b == 0) {
System.out.println(a);
System.exit(0);
}
long rem=a%b;
gcdFast(b, rem);
}
/* static long gcd(long a, long b) {
long best = 0;
for (long i = 1; i <= a + b; i++) {
if ((a%i ==0) && (b%i== 0))
best = i;
}
return best;
}
*/}
Algorithm 3 – Finding LCM of a number
import java.util.Scanner;
// GCD(a,b)*LCM(a,b)=a*b
public class LCM {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong(); // 8
long b = scanner.nextLong(); // 6
// long c = gcd(a, b);
// System.out.println("GCD is" + c);
long c = gcdFast(a, b);
long d = (a * b) / c;
System.out.println(d);
}
static long gcdFast(long a, long b) {
if (b == 0) {
return a;
}
long rem = a % b;
long c=gcdFast(b, rem);
return c;
}
/* static long gcd(long a, long b) {
long best = 0;
for (long i = 1; i <= a + b; i++) {
if ((a % i == 0) && (b % i == 0))
best = i;
}
return best;
}*/
}
