When I first saw this question I got quite intrigued and a bit #mindflabergasted. This sounds like something you could get asked on interviews. A very interesting question that can give quite a lot of insight about how important requirements and clear understanding of the problem can be.
Well first off, let us start with specifications and ambiguity as per usual. There’s a little dilemma in my head about the question. It can have to meanings:
- Find whether the array can be divided AS-IS, in that exact order into two equal-sum parts?
- Find whether the array can be divided in two equal-sum parts, independent of ordering, (meaning, whether you can find two subsets of the array that are of equal sum)
For the sake of developing our solution we will try to solve both and we will see how a small assumption early on, of one or the other, can lead to a totally different thought process, solution and, hence mistake if our interviewer was asking us the other one.
Find whether the array can be divided AS-IS, in that exact order into two equal-sum parts?
This should not be that hard, should it? So for the array to be divisible into two equal-sum parts in the same order, we need to have a point in the array where the subset to the left of that point will equal to the subset to the right and will equal to half of the total sum of the array.
Hence we can come up with an algorithm like this:
- Find the total sum of all elements in the array
- If sum is an odd number, return, the array cannot get divided
- Otherwise, go through the array keeping a left sum, until left sum is equal to half of the total sum
Sounds great! A quick analysis of the worst case scenario will give us:
- Time Complexity – Go through the list twice – O(n)
- Space Complexity – Keep a few variables – O(1)
Now let’s head into some easy coding and get this going. We’ll be using Java as per usual:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public boolean isArrayDividableInEqualSums(int[] fooBar) { if(fooBar == null) { return false; } int nSum = 0; int nLength = fooBar.length; for (int i = 0; i < nLength; ++i) { nSum += fooBar[i]; } if ((nSum % 2) != 0) { return false; // have an Odd number as a Sum, not possible to have 2 equal subsets } int nHalfSum = nSum / 2; int currSum = 0; for (int i = 0; i < nLength; ++i) { currSum += fooBar[i]; if (currSum == nHalfSum) { return true; // The set from the beginning up to and including i is equal to the elements from i+1 to the end } } return false; } |
Looks great! Can we improve? There does not seem to be a way to save on Time Complexity (O(n)) or Space Complexity (O(1)), but maybe we can imrpove something stylistically.
Let’s give it another try and make the code more readable.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
public boolean isArrayDividableInEqualSums(int[] fooBar) { if(fooBar == null) { return false; } int nSum = getArraySum(fooBar); int nHalfSum = nSum / 2; if (!isEvenNumber(nSum)) { return false; } return isSubsetFromBeginningEqualTo(nHalfSum, fooBar); } private int getArraySum(int[] glooBar) { int nSum = 0; int nLength = glooBar.length; for (int i = 0; i < nLength; ++i) { nSum += glooBar[i]; } return nSum; } private boolean isEvenNumber(int fooMan) { if ((fooMan % 2) == 0) { return true; } return false; } private boolean isSubsetFromBeginningEqualTo(int nTarget, int[] glooWasp) { int currSum = 0; int nLength = glooWasp.length; for (int i = 0; i < nLength; ++i) { currSum += glooWasp[i]; if (currSum == nTarget) { return true; } } return false; } |
Now our overall code is slightly longer, but the main method we wrote in Java is a lot shorter and a lot more readable. Indeed, I do not think we need the comments anymore, as someone just reading the code will probably understand exactly what is happening. Furthermore we have put different levels of abstraction in different methods, so our main one only shows a higher level understanding of the problem.
Sounds great, so now let us tackle the second problem…
Find whether the array can be divided in two equal-sum subsets, independent of ordering
Well if you followed me so far, you will probably think that this is going to be just straight forward generalization of the problem we were looking at before.
You know what, I am going to leave you with this for a few hours, see if you can come up with something. Remember all work is good work, even the one that does not lead to the correct result ;). Let me know your thoughts and solutions for this part!
EDIT: As someone stated below the best approach in this case (and IMO in a lot of cases where you have a to deal with subsets (i.e. n choose k)), is dynamic algorithm. So the idea behind it is fairly simple. The execution is a bit harder. The idea is we will have a 2D array with the array Size on one axis and the possible halfSum on the other. On each cell we will know if for that array size we can reach target number (in the half sum axis).
Here you have a piece of code that I came up with while trying to come up with a solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public boolean canBeDividedIntoTwoEqualSubsets(int[] gooBar) { int nSum = getArraySum(gooBar); if (!isEvenNumber(nSum)) { return false; } int nSize = gooBar.length; int nHalfSum = nSum / 2; boolean[][] nSubsetSumMap = new boolean[nHalfSum + 1][nSize + 1]; for (int i = 0; i < nSize + 1; ++i) { nSubsetSumMap[0][i] = true; } for (int i = 1; i < nHalfSum + 1; ++i) { nSubsetSumMap[i][0] = false; } for (int i = 0; i < nHalfSum; ++i) { for (int j = 1; j <= nSize; ++j) { nSubsetSumMap[i][j] = nSubsetSumMap[i][j-1] || nSubsetSumMap[i - gooBar[j-1]][j - 1]; } nSubsetSumMap[0][i] = true; } return nSubsetSumMap[nHalfSum][nSize]; } |
I ran it a few times and it seems to work flawlessly.
Hope you guys enjoyed it… and I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
Probably a very naive approach, since it will probably take O(2^n * (2n)) but might as well give it a shot!
So my thinking is, you have to try all possible combinations of adding/subtracting all the numbers in the array to see if there exists some way to add up to zero.
Make a new array of just 1s and -1s the size of the original array
Multiply the ith elements of original array and +/- array and sum up the result.
If result is zero, you get a yes
To make the +/- array, you need to go from 1 to 2^n, take the binary representation of that number, where the ith element in the array is the ith digit where 0 is stored as-1 and a 1 is just 1.
To go through all combinations, it’s 2^n time, and checking to see if the result is good, takes 2n time.
Good thinking. As it turns out the problem is NP-complete (although it sounds very similar to the other). I think with dynamic algorithm, trying to keep track of all previously seen sums, we could get a bit better time complexity.
To have two arrays means to have one that adds to half of the sum. So you need to know if there is sum/2 as a result of adding some elements. To see if you can get sum/2 you take each number and ask if you can get sum/2-number with adding remaining elements and recursion will do its thing.
Yep that algorithm sounds great.
– check if sum is even, then
– you can also have the sort the elements, if the biggest element is bigger than sum/2 .. then it’s not possible, otherwise
– you do binary search for (sum/2 – biggest) = x , then you take the biggest value smaller than or equal to x , and look for the difference, and so on till either you difference becomes 0 or you find x
– sorting is O(n lg n) , searching at most n/2 times < O (n lg n).
– I feel it works