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]);
       }         

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.

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.

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.