Solved

splitArray  challenge

Posted on 2016-09-27
6
99 Views
Last Modified: 2016-10-17
Hi,

 I am working on below challenge
http://codingbat.com/prob/p185204

splitArray
prev  |  next  |  chance


Given an array of ints, is it possible to divide the ints into two groups, so that the sums of the two groups are the same. 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 splitArray(). (No loops needed.)

splitArray([2, 2]) → true
splitArray([2, 3]) → false
splitArray([5, 2, 3]) → true

I was not clear on how many elements each group should have? please advise
0
Comment
Question by:gudii9
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
6 Comments
 
LVL 44

Accepted Solution

by:
AndyAinscow earned 167 total points (awarded by participants)
ID: 41818380
>>I was not clear on how many elements I should take for each group.

You need to take as many as you need for each group BUT you must use all given ints.
1
 
LVL 56

Assisted Solution

by:Bill Prew
Bill Prew earned 167 total points (awarded by participants)
ID: 41820425
One FALSE case that is easy to identify is if the sum of all the integers in the input array sum up to an odd number then immediately return FALSE, since there would be no way way that two numbers added together could result in an odd number.  So for efficiency I might do that test up front.

Beyond that I'd be happy to comment on pseudo code of java once you get started on this, there area number of ways to attack it. You might get some inspiration from the following:

https://en.wikipedia.org/wiki/Partition_problem

~bp
1
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 166 total points (awarded by participants)
ID: 41820683
If you are struggling to understand the Partition_problem link that Bill showed, do not take it to heart since "NP-hard problem" are one of the hardest type algorithms to understand in Computer Science.

As Bill pointed out, you know that if there is a solution then S = sum(all the integers) must be even. Now that you have established that, Let T = S/2. Now, if you can find a subset of the integers whose sum is T, then you are done, since the other integers not in your chosen subset must also have a sum equal to T (since the sum of both subsets must be 2*T, which is equal to S.

Taking one of your examples..
splitArray([5, 2, 3]) → true
S = 10 --> T = 10/2 = 5.
Since 5 is an element in the set of integers, it must be that the remaining elements not in the subset of {5} must sum up to 5. Check: {2,3} --> Sum is also 5 (no surprise). This is one of the simpler examples in determining the solution, since, in general, you cannot expect that the number T to appear in the set of integers.
1

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

635 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question