Euclid's Algorithm to find Greatest Common Divisor

Objective: Given 2 number m and n, we have to find Greatest Common Divisor.

Approach: Euclid's Algorithm to find Greatest common Divisor. Suppose m and n is two integer, m > n. 
1. Get reminder while divide m by n, if it 0 then we have our answer n as GCD.
2. If reminder is not 0, then divide m by n and then get reminder. Thereafter, set reminder to n = r; m = n; and repeat step 1 to get GCD of 'm' and 'n'.

Solution: Java Code

	public class EuclidAlgo {
	public static void main(String ...arg) {
	Scanner scanner = new Scanner(System.in);
	int m = scanner.nextInt();
	int n = scanner.nextInt();
	System.out.println("GCD: "+ gcd(m, n));
	}
	private static int gcd(int m, int n) {
	int r = m % n;
	int q = m / n;
	if(r == 0) return n;
	return gcd(n, r);
	}
	}

view raw EuclidAlgo.java hosted with ❤ by GitHub

 

Permutation of two String in ordered form

Objective: Generate permutation of two string in ordered form. e.g. if "abc" and "def" is two strings, we need to generate all permutation having these two string characters the only condition if "a" come before "b" then its must come before "b" in the permutations.
i.e. "adebfc", "abcdef", "daebcf" and so on are permutation of these string.

Approach: As we can see either we start with first string or second string, but we need to maintain each string character order in our permutation.

In general, we can say that all permutation either start with first string character or second string character.

i.e. if "abc" and "def" is two strings then, 

perumation("abc", "def") = ("a" + permutation("bc", "def")) and ("d" + permutation("abc", "ef")

Solution: Java Code

	public class GeneratePermutation2Strings {
	public static void main(String... arg) {
	Scanner scanner = new Scanner(System.in);
	String s1 = scanner.nextLine();
	String s2 = scanner.nextLine();
	generateSequence("", s1, s2);
	}
	private static void generateSequence(String prefix, String s1, String s2) {
	if(s1.length() + s2.length() == 0) {
	System.out.println(prefix);
	}
	if(s1.length() > 0) {
	String temp1 = s1.length() <= 1 ? "" : s1.substring(1, s1.length());
	generateSequence(prefix + (s1.length() > 0 ? s1.charAt(0) : ""),temp1 , s2);
	}
	if(s2.length() > 0) {
	String temp2 = s2.length() <= 1 ? "" : s2.substring(1, s2.length());
	generateSequence(prefix + (s2.length() > 0 ? s2.charAt(0) : ""), s1, temp2);
	}
	}
	}

view raw GeneratePermutation2Strings.java hosted with ❤ by GitHub