Ravi
BAN USERWorking on eclipse plugin development
By window, I am assuming that is a contiguous set of numbers in A.
Brute Force Algo
There are a total of n-m+1 such subsets of A whose length is m. Since the length of the required window is greater than or equal to m, then the number of windows to evaluate is sigma(n-k+1) where k runs from m to n which is quadratic in nature.
Sounds like we could use greedy strategies to intelligently eliminate looking at all subsets depending on the knowledge of what we have gained till then.
One possible input to the greedy measure is that since the windows is the smallest, the starting and end elements of A should be a member of B.
Some thoughts.. Not complete though..
Assume a set S (hashset) which contains the list of all 4 digit prime numbers.
Now in N1 try to change last digit to match with N2. Check if the resultant number is prime. If yes repeat it for the remaining digits. If not, try with 2,3,4 placed digits. If the resultant number is not a prime for any of the digits, figure a prime number that can be obtained by changing only one digit of N1. Repeat the process.
Pseudo Code
char[] n1 = new char[4];
char[] n2 = new char[4];
while (n1 != n2) {
char[] tmp = new char[4];
tmp[0] = n1[0];
tmp[1] = n1[1];
tmp[2] = n1[2];
tmp[3] = n2[3];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[2] = n2[2];
tmp[3] = n1[3];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[1] = n2[1];
tmp[2] = n1[2];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
tmp[0] = n2[0];
tmp[1] = n1[1];
if (isTmpPrime(tmp)) {
n1 = tmp;
} else {
n1 = getNextPrime(n1);
}
}
}
}
}
Let the two arrays be A1 and A2 and their medians be m1 and m2. Find all elements between m1 and m2 and then find their median.
- Ravi May 28, 2010