Yong.Christopher.Tang
BAN USERJava Codes
/**
* This function finds how many and where the elements are missing in an arithmetic progression.
* Its time complexity is O(n) and space complexity is O(1).
*
* If missing elements need to be specified, an additional array buffer is necessary for the task which makes
* the space complexity O(n).
*/
double[] locateMissingElements(double[] ap) {
if (ap == null) {
return null;
}
if (ap.length < 3) {
return ap;
}
double commonDiff = ap[ap.length - 1];
for (int i = 0; i < ap.length - 1; i++) {
ap[i] = ap[i + 1] - ap[i];
if (Math.abs(ap[i]) < Math.abs(commonDiff)) {
commonDiff = ap[i];
}
}
ap[ap.length - 1] = 0;
// if the common diff is 0, technically no elements are actually missing. Just make this an exception case.
if (commonDiff == 0) {
return null;
}
// how many elements are missing between index n and n+1
for (int i = 0; i < ap.length; i++) {
ap[i] = ap[i] / commonDiff - 1;
}
return ap;
}
- Yong.Christopher.Tang January 09, 2016