Problem
This finds the equilibrium. For sum/mult an equilibrium is defined as the index i at which sum/mult of all elements at index < i is same as sum/mult of all elements of at index > j respectively. Edge cases are documented clearly in JavaDocs.
Note: I do understand merits of unit testing in separate files. But deliberately added it to main method for personal convenience, so I request that you don’t consider that in your feedback.
I’m looking for request code review, optimizations and best practices.
public final class EquilibriumIndex {
private EquilibriumIndex() {}
/**
* Returns index, if equilibrium is found, else returns 0.
* If multiple equilibrium exists then, the first equilibrium is returned.
* Note: end of array is also treated as an equilibrium.
*
* Eg - 1:
* [-7, 8, -2, 8, -7, 0]
* has 2 equilibrium
* a[2] = -2;
* a[5] = 0;
* in such case position 2 is returned
*
* Eg -2:
* [0, -7, 8, -2, 8, -7]
* has 2 equilibrium
* a[0] = 0;
* a[3] = -2;
* in such case position 0 is returned
*
* @param a the int array
* @returns the index if found, else returns -1.
*/
public static int getSumEquilibrium(int[] a) {
int sum = 0; // the sum of all contents
int leftSum = 0; // the sum which starts from the left side.
for (int i : a) {
sum += i;
}
for (int i = 0; i < a.length; i++) {
sum -= a[i];
if (sum == leftSum) {
return i;
}
leftSum += a[i];
}
return -1;
}
private static int processZero (int[] a, int i) {
// if index i is the first element of the array.
if (i == 0) {
for (int j = i + 1; j < a.length; j++) {
// eg: [0, 1, 2, 0, 5], equilibrium is the first element.
if (a[j] == 0) {
return 0;
}
}
//eg: [0, 1, 2, 3], equilibrium is the last element.
return a.length - 1;
} else {
// if 0 is not the first element of the array then the first element of array is smallest equilibrium
// eg: [0, 1, 2, 3]
return 0;
}
}
/**
* Returns index, if equilibrium is found, else returns 0.
* If multiple equilibrium exists then, the first equilibrium is returned.
* Note: end of array is also treated as an equilibrium.
*
* Eg - 1:
* [0, 8, -2, 0]
* has 2 equilibrium
* a[0] = 0;
* a[1] = 8;
* a[2] = -2;
* in such case position 0 is returned
*
* @param a the int array
* @returns the index if found, else returns -1.
*/
public static double getMultEquilibrium(int[] a) {
/*
* double chosen to prevent int-overflow.
* http://programmers.stackexchange.com/questions/188721/when-do-you-use-float-and-when-do-you-use-double
*/
double product1 = 1;
double leftProduct = 1;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
return processZero(a, i);
}
product1 = product1 * a[i];
}
for (int i = 0; i < a.length; i++) {
product1 = product1 / a[i];
if (product1 == leftProduct) return i;
leftProduct = leftProduct * a[i];
}
return -1;
}
public static void main(String[] args) {
// testing sum
int[] a1 = {0, -7, 8, -2, 8, -7};
assertEquals(0, EquilibriumIndex.getSumEquilibrium(a1));
int[] a2 = {-7, 8, -2, 8, -7, 0};
assertEquals(2, EquilibriumIndex.getSumEquilibrium(a2));
int[] a3 = {-7, 1, 5, 2, -4, 3, 0};
assertEquals(3, EquilibriumIndex.getSumEquilibrium(a3));
// edge case.
int[] a4 = {-7, 1, 5, 2, -4, 3, 10};
assertEquals(6, EquilibriumIndex.getSumEquilibrium(a4));
// no-equilibrioum
int[] a5 = {-7, 15, 5, 2, -4, 3, 10};
assertEquals(-1, EquilibriumIndex.getSumEquilibrium(a5));
int[] a6 = {10, 4, -20, 30};
assertEquals(1, EquilibriumIndex.getSumEquilibrium(a6));
// testing mult
int[] a7 = {0, 1, 2, 3, 4};
assertEquals(4, EquilibriumIndex.getMultEquilibrium(a7), 0);
int[] a8 = {0, 0, 1, 2, 3, 4};
assertEquals(0, EquilibriumIndex.getMultEquilibrium(a8), 0);
int[] a9 = {0, 0, 2, 3, 0, 4};
assertEquals(0, EquilibriumIndex.getMultEquilibrium(a9), 0);
int[] a10 = {0, 1, 2, 3, 0};
assertEquals(0, EquilibriumIndex.getMultEquilibrium(a10), 0);
int[] a11 = {1, 2, 0, 4, 5};
assertEquals(0, EquilibriumIndex.getMultEquilibrium(a11), 0);
int[] a12 = {1, 2, 4, 5, 0};
assertEquals(0, EquilibriumIndex.getMultEquilibrium(a12), 0);
int[] a13 = {2, 20, 5, 10, 4};
assertEquals(2, EquilibriumIndex.getMultEquilibrium(a13), 0);
int[] a14 = {2, 10, 5, 4, 5, 1};
assertEquals(2, EquilibriumIndex.getMultEquilibrium(a14), 0);
int[] a15 = {1, 2, 3, 4, 5};
assertEquals(-1, EquilibriumIndex.getMultEquilibrium(a15), 0);
}
}
Solution
getMultEquilibrium() is supposed to return an array index (or -1 if there is no such index). It makes no sense that the array index be a double, as array indexes must be ints. Therefore,
public static double getMultEquilibrium(int[] a)
should be
public static int getMultEquilibrium(int[] a)
To prevent int-overflow, you can instead use the datatype long.
Then you don’t have to go through the hassle of floating-point-arithmetics.
Furthermore you could extract a guard-clause in your processZero-method to reduce nesting level by one:
private static int processZero (int[] a, int i) {
// if 0 is not the first element of the array then the first element of array is smallest equilibrium
// eg: [0, 1, 2, 3]
if (i != 0) {
return 0;
}
for (int j = i + 1; j < a.length; j++) {
// eg: [0, 1, 2, 0, 5], equilibrium is the first element.
if (a[j] == 0) {
return 0;
}
}
//eg: [0, 1, 2, 3], equilibrium is the last element.
return a.length - 1;
}
I’ve had a look at your code, and come up with the following suggestions.
Firstly, rename your variables to something meaningful:
public static double getMultEquilibrium(int[] a
change this too:
public static double getMultEquilibrium(int[] currentArray)
Yes, this does increase the size of your code somewhat, but it is a best practice to always name variables with a name that describes its function. This is my main quibble with your code, because it makes it hard to read.
Another example is:
double product1 = 1;
double leftProduct = 1;
Yes, these variables represent various multiplications, but perhaps be a little more specific.
Secondly, although I don’t get the point of doing this calculation, it seems that it would be fairly easy to convert to some sort of recursive divide and conquer strategy to find the equilibrium. That would be much more efficient, and (I imagine) would result in a reduction in all the nested if‘s and for loops inside each other.
Other than that your code seems alright.
Not enough precision
For the sum case, you need to use longs for your sums otherwise you will get overflows. This assumes that your input is smaller than 2^32 elements, otherwise you will need even more precision.
For the multiply case, neither a double or a long will save you from overflows/precision loss, even with only a few elements. To fix this, you can either use BigInteger, or you can do something tricky where you decompose each number into a list of its prime factors.
Your comments
First, it would be nice if your comments actually explained what an equilibrium was. Your question did so, but someone reading your code by itself would have no idea.
Second, there were a couple of errors in your comments. In this multiplication example:
[0, 8, -2, 0]
you stated that there were 3 equilibria, but I believe that a[3] qualifies as a 4th.
In the comments for processZero(), you had this comment:
// if 0 is not the first element of the array then the first element of array is smallest equilibrium
// eg: [0, 1, 2, 3]
but in that example, 0 was the first element so it wasn’t a good example.
Inconsistency
You did this which I like:
leftSum += a[i];
But later did this which I don’t like, and which is inconsistent with your previous code:
leftProduct = leftProduct * a[i];
Things I liked
In general, your program was well commented. Also, the algorithms you used seemed to be the best ones that took only O(N) time. I didn’t have any problems understanding what your code was doing.