Java > Recursion-2 > splitOdd10 (CodingBat Solution)

Problem:

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


Solution:

public boolean splitOdd10(int[] nums) {
  int index = 0;
  int sum1 = 0;
  int sum2 = 0;
  return recArray(nums, index, sum1, sum2);
}

private boolean recArray ( int[] nums, int index, int sum1, int sum2 ) {
  if ( index >= nums.length ) {
    return (sum1%10 == 0 && sum2%2 !=0) || (sum2%10 == 0 && sum1%2 !=0);
  }

  int value = nums[index];

  return (recArray(nums, index + 1, sum1 + value, sum2) || 
    recArray(nums, index + 1, sum1, sum2 + value));
}


9 comments :

  1. public boolean splitOdd10(int[] nums) {
      return groupSum(0,nums,0,0);
    }
    private boolean groupSum(int start,int[] nums,int sum1,int sum2) {
      if (start >= nums.length) return (sum1%10==0 & sum2%2==1)|(sum1%2==1 & sum2%10==0);
      if (groupSum(start+1,nums,sum1+nums[start],sum2)) return true;
      if (groupSum(start+1,nums,sum1,sum2+nums[start])) return true;
      return false;
    }

    ReplyDelete
  2. public boolean splitOdd10(int[] nums) {

    return helper(0,nums,0,0) ;
    }

    public boolean helper(int start, int[] nums, int sum1, int sum2){
    if(start == nums.length)
    return sum1 % 10 == 0 && sum2 % 2 == 1 ||
    sum2 % 10 == 0 && sum1 % 2 == 1;


    return helper(start + 1, nums, sum1 + nums[start], sum2) ||
    helper(start + 1, nums, sum1, sum2 + nums[start]) ;
    }

    ReplyDelete
  3. public boolean splitOdd10(int[] nums) {
    int sum = 0;
    for(int i = 0; i < nums.length; i++)
    sum += nums[i];
    return sum % 2 == 1;
    }

    ReplyDelete
    Replies
    1. But it doesn't check if sum of a group is a multiple of 10

      Delete
  4. private final boolean splitOdd10(int[] nums) {
    return groupSum(0, nums, 0, 0);
    }
    private final boolean groupSum(int start,int[] nums,int sum1,int sum2) {
    if (start >= nums.length){
    return (sum1 % 10 == 0 && sum2 % 2 == 1)
    || (sum2 % 10 == 0 && sum1 % 2 == 1);
    }
    return groupSum(start + 1, nums, sum1 + nums[start], sum2)
    || groupSum(start + 1, nums, sum1, nums[start] + sum2);
    }

    ReplyDelete
  5. public boolean splitOdd10(int[] nums) {
    return helper(0, nums, 0, 0);
    }

    public boolean helper(int start, int[] nums, int mod, int odd) {
    if (start >= nums.length)
    return mod%10 == 0 && odd%2 == 1;
    return helper(start+1, nums, mod + nums[start], odd) || helper(start+1, nums, mod, odd + nums[start]);
    }

    ReplyDelete
    Replies
    1. You dont need an "or" in the return end case because both cases of mod, odd and odd, mod as the separate sums will be reached so this does work in all cases although may take extra recursive calls sometimes

      Delete
  6. public boolean splitOdd10(int[] nums) {
    return helper(nums, 0, 0, 0);
    }
    private boolean helper(int[] nums, int start, int g1, int g2) {
    int len = nums.length;
    if(start>=len) {
    return ((g1%10==0 && g2%2==1)||( g2%10==0 && g1%2==1));
    }
    int number = nums[start];
    return helper(nums, start+1, g1+number, g2)||helper(nums, start+1, g1, g2+number);
    }

    ReplyDelete
    Replies

    1. Here's how it works:

      - The `splitOdd10` function is the main function that takes an array of integers as input and calls the helper function with initial parameters.

      - The `helper` function is a private function that does the main work. It takes four parameters: the array of integers, the starting index for the recursion, and two groups (g1 and g2) which will hold the sums of the two groups of numbers.

      - The base case for the recursion is when the starting index is greater than or equal to the length of the array. At this point, it checks if one group's sum is a multiple of 10 and the other group's sum is odd. If this condition is met, it returns true; otherwise, it returns false.

      - If the base case is not met, it takes the number at the current starting index and recursively calls the helper function twice: once adding the number to g1's sum and once adding it to g2's sum. If either call returns true, then it returns true; otherwise, it returns false.

      This code uses a common recursive pattern for problems where you need to explore all possible combinations or permutations of an array. It's a depth-first search because it explores one path fully before backing up and exploring another path.

      Delete

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact