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));
}
public boolean splitOdd10(int[] nums) {
ReplyDeletereturn 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;
}
public boolean splitOdd10(int[] nums) {
ReplyDeletereturn 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]) ;
}
public boolean splitOdd10(int[] nums) {
ReplyDeleteint sum = 0;
for(int i = 0; i < nums.length; i++)
sum += nums[i];
return sum % 2 == 1;
}
But it doesn't check if sum of a group is a multiple of 10
Deleteprivate final boolean splitOdd10(int[] nums) {
ReplyDeletereturn 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);
}
public boolean splitOdd10(int[] nums) {
ReplyDeletereturn 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]);
}
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
Deletepublic boolean splitOdd10(int[] nums) {
ReplyDeletereturn 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);
}
DeleteHere'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.