Splitting an array in 2 parts such that one part sums to a multiple of 10 and other sums to an odd number

Question

Given an array of ints, is it possible to divide the ints into two groups, so that the sum of one group is a multiple of 10, and the sum of the other group is odd. Every int must be in one group or the other. Write a recursive helper method that takes whatever arguments you like, and make the initial call to your recursive helper from splitOdd10(). (No loops needed.)

splitOdd10({5, 5, 5}) → true
splitOdd10({5, 5, 6}) → false
splitOdd10({5, 5, 6, 1}) → true

public boolean splitOdd10(int[] nums) {
 int total=findSum(0, nums, 0);
 if((total%10)%2==0||total==0)
 {
 return false;
 }
 return ifGroupExistsThatSumsToValue(0, nums, total%10);
 }
 public int findSum(int n, int[] nums, int sum)
 {
 if(nums.length==0)
 return 0;
 if(n==nums.length-1)
 {
 return sum+nums[n];
 }
 return findSum(n+1, nums, sum+nums[n]);
 }
 public boolean ifGroupExistsThatSumsToValue(int start, int[]nums, int target)
 {
 if(start==nums.length-1)
 {
 return target-nums[start]==0;
 }
 if(target==0)
 {
 return true;
 }
 if(ifGroupExistsThatSumsToValue(start+1, nums, target-nums[start]))
 return ifGroupExistsThatSumsToValue(start+1, nums, target-nums[start]);
 return ifGroupExistsThatSumsToValue(start+1, nums, target+nums[start]);
 } 

• Martin R: Perhaps you should mention that this is from codingbat.com/prob/p171660.
• Florian F: I assume the multiple of 10 must be non-empty? If not, the solution is trivial.
• David Mulder: @Anirudh: Copyright/Plagiarism ;-)
• Landei: (total % 10) % 2==0 is exactly the same as total % 2==0.
• miracle173: I think if you paste and copy a text into your text without mentioning the source than this is plagiarism.

Answer 1

You could simplify findSum. I would also rename the variables and reorder the parameters:

private int findSum(int[] nums, int i, int accum) {
 if (i == nums.length) {
 return accum;
 }
 return findSum(nums, i + 1, nums[i] + accum);
}

---

The end part of the ifGroupExistsThatSumsToValue method can also be simplified:

public boolean ifGroupExistsThatSumsToValue(int start, int[] nums, int target) {
 if (start == nums.length - 1) {
 return target - nums[start] == 0;
 }
 if (target == 0) {
 return true;
 }
 return ifGroupExistsThatSumsToValue(start + 1, nums, target - nums[start])
 || ifGroupExistsThatSumsToValue(start + 1, nums, target + nums[start]);
}

---

When logic is kind of tricky, like in this problem, it's good to add the examples in the problem statement as proper unit tests:

@Test
public void test_5_5_5() {
 assertTrue(splitOdd10(new int[]{5, 5, 5}));
}
@Test
public void test_5_5_6() {
 assertFalse(splitOdd10(new int[]{5, 5, 6}));
}
@Test
public void test_5_5_6_1() {
 assertTrue(splitOdd10(new int[]{5, 5, 6, 1}));
}

And then keep adding some more to try to cover all corner cases, for example:

@Test
public void testEmpty() {
 assertFalse(splitOdd10(new int[0]));
}
@Test
public void testSingleNum() {
 assertTrue(splitOdd10(new int[]{1}));
 assertFalse(splitOdd10(new int[]{2}));
 assertFalse(splitOdd10(new int[]{10}));
}

---

As others have pointed out, your formatting is awful. Please reformat nicely next time, Control Shift f in Eclipse does this easily, and any decent IDE has the equivalent.

---

To be honest, I don't really understand why splitOdd10 and ifGroupExistsThatSumsToValue have to be so complicated. If I simply follow the problem description in a straightforward way and just try to add up the numbers from left to right and check the conditions, I arrive at something that's much shorter and easier to understand:

private boolean splitOdd10(int[] nums) {
 return splitOdd10(nums, 0, 0, findSum(nums, 0, 0));
}
private boolean splitOdd10(int[] nums, int i, int left, int right) {
 return left % 10 == 0 && right % 2 == 1
 || i < nums.length && splitOdd10(nums, i + 1, left + nums[i], right - nums[i]);
}

I'm wondering if I'm missing something. Both your and my solutions are passing all my unit tests.

• Anirudh: Yes! It's not really required to make another method for sum. Your solution should work all the way. Btw regarding formatting I wrote it on plane text though I did my best to separate an indented block by 4 spaces every time but it all got messed up while copy pasting here in the question.

Answer 2

Calling ifGroupExistsThatSumsToValue twice

You don't need to call ifGroupExistsThatSumsToValue inside the if and then again afterwards. The normal approach to avoid calling an expensive function twice would be to save the result in a varible and then use that. But in this case, just do this:

 if (ifGroupExistsThatSumsToValue(start + 1, nums, target - nums[start])) {
 return true;
 }

findSum

The question doesn't say that this must be done recursively, so I would use an iterative approach as it is faster and easier to read.

Formating

It is customary to put spaces between assignments, comparisons, additions, etc. So for example if((total%10)%2==0||total==0) should be if ((total % 10) % 2 == 0 || total == 0) { (an IDE will format you code for you)

Curly Braces

I'm going to quote myself on this one:

I think that not using curly braces around one-line if statements is bad and can easily lead to bugs. Others disagree, but I think that it should at least be handled consistently. You use them in some places and not in others, which is unexpected.

• Anirudh: Agreed on the spacing part. Think I cramped it for space and in case of multiple or indented braces one should add spaces for more readability. Would appreciate if you could ass the iterative solution in the review.
• tim: the iterative solution for getting the sum of array values is just iterating over the array and adding its values in an accumulator variable. See @Adrian Jandls answer for the code.
• Anirudh: Ahh okay! Well for the sum you could do it but the challenge states "no loops" in the end.
• tim: My understanding was that no loops should be used for the recursive helper method. But you are right, it could also mean that there should be no loops at all in the code, in which case your approach is correct.
• Anirudh: Damn I just realized that I made a really embarrassing typo in my first comment ..*add sheesh!

Answer 3

This review is based solely on style, not on the algorithm at hand.

The task does not state that the sum function needs to be recursive. While it may be good practice for this task a simple for loop should suffice.

int sum = 0;
for(int i = 0;i<nums.length;i++)
{
 sum+=nums[i];
}
return sum;

Additionally you should never use one-lined if-clauses without braces. See this question for why. If you decide not to follow this practice, you should atleast stay consistent in your code. At the moment you sometimes use brackets for one-lined ifs and sometimes you don't.