Amazon student Interview Question
StudentsCountry: United States
Interview Type: Phone Interview
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);
}
}
}
}
By gradually enlarging the difference of two expected numbers....
- Moron March 20, 2012void 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--;
}
}