CareerCup

By gradually enlarging the difference of two expected numbers....


void mindiff(int n){

int x, y = sqrt(n);
while(true){
if( x*y <= n+2 && x*y >=n )
break;
else if(x*y<n) // suppose x is always bigger number;
x++;
else
y--;
}


}

Trivial solution:
1) x*y can have values only in the set S = {n,n+1,n+2}
2) For each value in set S, find pairwise factors (a,b). Keep a min of |a-b|.

The complexity of finding all pairwise factors of a number 'n' = O(n/2)

Naive approach will be

Get the divisor (x,y ) of n,n+1 and n+2 and then keep track minimum of them s.t |x-y| would be minimum

public class Factors {
	public static void main(String args[]) {
		printMinDiffFactors(19); // A = 4 & B = 5
		printMinDiffFactors(100); // A = 10 & B = 10
		printMinDiffFactors(82); // A = 7 & B = 12
		printMinDiffFactors(46); // A = 6 & B = 8
	}

	private static Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

	public static void printMinDiffFactors(int input) {
		pairs = new HashMap<Integer, Integer>();
		for (int i = 2; i * i <= (input + 2); i++) {
			updatePairs(i, input);
			updatePairs(i, input + 1);
			updatePairs(i, input + 2);
		}

		int minA = input;
		int minB = 1;
		for (Map.Entry<Integer, Integer> a : pairs.entrySet()) {
			if (Math.abs(a.getKey() - a.getValue()) < Math.abs(minA - minB)) {
				minA = a.getKey();
				minB = a.getValue();
			}
		}
		System.out.println("printMinDiffFactors(" + input + "): A = " + minA
				+ " & B = " + minB);
	}

	public static void updatePairs(int aFactor, int input) {
		int count = 0;
		int num = input;
		if (num % aFactor == 0) {

			while (num % aFactor == 0) {
				num = num / aFactor;
				count++;
			}
			int a = 1;
			for (int j = 1; j <= count; j++) {
				a *= aFactor;
				pairs.put(a, input / aFactor);
			}
		}
	}

}