4

I had a recursion interview question problem in Java,Need your help on this.

Write a **Java function** such that :: Given an array of ints, is it possible to divide the ints into two groups, so that the sum of the two groups is the same, with these constraints: all the values that are multiple of 5 must be in one group, and all the values that are a multiple of 3 (and not a multiple of 5) must be in the other. (No loops needed.)

split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true

PS:This was a Interview Question for hewlett packard

Improve this question
12
  • question is not clear for me...i got this interview question and i dont know how to proceed Commented Dec 16, 2010 at 12:10
  • 1
    wait until they make you do this problem and fizz buzz together Commented Dec 16, 2010 at 12:39
  • the spec sounds quite clear to me, start hacking on it and post your code when you can not get any further. Commented Dec 16, 2010 at 12:42
  • It's your interview and if you start handing in other people's answers, your (possible) future employer might think you know more than you actually do. Commented Dec 16, 2010 at 12:46
  • 2
    @Deepak, if the question is unclear, why not ask for clarification to those who posed the question? Commented Dec 16, 2010 at 12:48

5 Answers 5

Reset to default
4

The question can be easily reduced to following: given a set of integers numbers and an integer target, is it possible to find a subset of numbers with sum equal to target?
Let me know if transition needs clarification.

It can be solved with DP in O(numbers.size * target) time. The idea is following

  1. When numbers.size is 0, the only reachable sum is 0.
  2. Suppose we have numbers == {1, 3}, in this case sums {0, 1, 3, 4} are available. What if we add another element to numbers, 4? Now, all old sums can still be reached and some new ones too: {0 + 4, 1 + 4, 3 + 4, 4 + 4}. Thus, for numbers == {1, 3, 4}, available sums are {0, 1, 3, 4, 5, 7, 8}.
  3. In this fashion, adding number by number, you can build the list of reachable sums.

A working example (it doesn't handle negative numbers, but you can easily fix that)

boolean splittable(int[] numbers, int target) {
    boolean[] reached = new boolean[target + 1];
    reached[0] = true;

    for (int number : numbers) {
        for (int sum = target - 1; sum >= 0; --sum) {
            if (reached[sum] && sum + number <= target) {
                reached[sum + number] = true;
            }
        }
    }

    return reached[target];
}

Run it

System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true
System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false

edit
I just noticed the "recursion" part of the requirement. Well, DP can be rewritten as recursion with memoization, if that's the hard requirement. This would preserve runtime complexity.

edit 2
On groups. You have to assign elements divisible by 3 or 5 to respective groups before you proceed with the algorithm. Let's say, sum of all elements is s, sum of elements divisible by 3 is s3 and sum of elements divisible by 5 but not 3 is s5. In this case, after you assigned those 'special' elements, you have to split the rest that sum in one group is s/2 - s3 and in another s/2 - s5.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Although not recursive, it is a neat solution.
@Nikita Thanks for your impeccable reply
@Nikita,I have a clarification.i dont see 2 groups which contains elements which are only multiples of 3 and other group which are only multiples of 5,though the solution gives the idea of summation.my actual requirement says i need 2 different groups such that one is multiples of 5 and other is multiples of 3 only.Please clarify
@Deepak I've clarified how to deal with 3's and 5's in the post.
@Nikita,i would be thankful to you if you could explain in the same code example which you have posted as to how will you accomplish the grouping of s3 and s5.im a bit confused with the grouping.
|
1

Very slow, but working solution:

static boolean canSplit(int[] arr, int lvl, int sum1, int sum2) {
        if (arr.length == lvl) {
            if (sum1 == sum2) {
                return true;
            } else {
                return false;
            }
        }
        if (arr[lvl] % 5 == 0) {
            return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2);
        } else if (arr[lvl] % 3 == 0) {
            return canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
        }
        return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2) ||
               canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
    }

Call the function:

canSplit(arr, 0, 0, 0);
Improve this answer

Comments

1

Code that would probably get me fired. But will work :D

Entirely recursive, equally deadly.

public boolean split53(int[] nums) {
    return split_fn(0, nums, 0, 0, false, false);
}
public boolean split_fn(int start, int[] nums, int left, int right, boolean fiveLeft, boolean chosen) {
    if (start >= nums.length) {
        if (left == right) return true;
        return false;
    }
    if (nums[start] % 5 == 0) {
        if (!chosen) {
            return split_fn(start + 1, nums, left + nums[start], right, true, true) || split_fn(start + 1, nums, left, right + nums[start], false, true);
        } else {
            return split_fn(start + 1, nums, left + ((fiveLeft) ? nums[start] : 0), right + ((!fiveLeft) ? nums[start] : 0), fiveLeft, chosen);
        }

    }

    if (nums[start] % 3 == 0 && nums[start] % 5 != 0) {
        if (!chosen) {
            return split_fn(start + 1, nums, left + nums[start], right, false, true) || split_fn(start + 1, nums, left, right + nums[start], true, true);
        } else {
            return split_fn(start + 1, nums, left + ((!fiveLeft) ? nums[start] : 0), right + ((fiveLeft) ? nums[start] : 0), fiveLeft, chosen);
        }
    }
    //standard case
    return split_fn(start + 1, nums, left + nums[start], right, fiveLeft, chosen) || split_fn(start + 1, nums, left, right + nums[start], fiveLeft, chosen);

}
Improve this answer

Comments

1

Here is the real recursive solution.

private boolean split2(int index, int[] nums, int sum1, int sum2) {
  if (index >= nums.length) {
    return sum1 == sum2;
  }

  if (split2(index + 1, nums, sum1 + nums[index], sum2)) {
    return true;
  }
  if (split2(index + 1, nums, sum1, sum2 + nums[index])) {
    return true;
  }

  return false; 
}

This code goes through puting every element into one of the group. If in any combination the two groups are equal it returns true. No loops used and in only one function.

Best for all

edit: Your function takes 4 arguments as input whereas the question gets as input only the array. You have to specify that the desired function could be done using yours with the call split2(0,nums,0,0);

Improve this answer

1 Comment

This answer is irrelevant. Does not take into account the multiples of 3 and 5 requirement.
0

I don't know how fast or slow the following solution is. But precisely it is a recursive backtracking solution, which uses no loops as mentioned in the question.

Here is the code snippet:

public boolean split53(int[] nums) {
    int start = 0, firstPart = 0, secondPart = 0;
    if (split(start, nums, firstPart, secondPart)) {
        return true;
    }
    return false;
}

public boolean split(int start, int[] nums, int firstPart, int secondPart) {
    if (start >= nums.length) {
        return (firstPart == secondPart);
    }
    if ((start + 1) < nums.length
            && (nums[start] % 3 != 0)
            && (nums[start + 1] % 5 != 0)
            && split(start + 2, nums, firstPart + nums[start], secondPart
                    + nums[start + 1])) {
        return true;
    }
    if ((start + 1) < nums.length
            && (nums[start + 1] % 3 != 0)
            && (nums[start] % 5 != 0)
            && split(start + 2, nums, firstPart + nums[start + 1],
                    secondPart + nums[start])) {
        return true;
    }
    if ((nums[start] % 3 != 0)
            && split(start + 1, nums, firstPart + nums[start], secondPart)) {
        return true;
    }
    if ((nums[start] % 5 != 0)
            && split(start + 1, nums, firstPart, secondPart + nums[start])) {
        return true;
    }
    return false;
}

Hope it helps.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.