×

# Split an even-size array into two sets of equal length and equal sum of their elements.

 0 There was a weekly challenge question on TECHGIG. Question was something like-" There is an array of odd size (size<100000). You have to remove any one element from the array, so that array becomes even in size. Now check whether, it is possible to divide the even size array into two equal size set so that total sum of the elements of each set is same. Return 1 if it is possible, otherwise return -1". How to approach this question? Since size of array was quite large, so, using Dp approach just like "subset sum problem" (having time complexity O(sum*sizeof_array)) seemed to be quite expensive. asked 15 Jul '17, 01:50 36●4 accept rate: 6%

 0 Can you please provide exact problem statement? I believe you are missing something quite important here with your description of the problem. In general, task which you described is most likely unsolvable. One can show that being able to solve it for array of doubles / array of intergers upto 1e18 means being able to solve 0/1 knapsack problem which is NP. However, it may get completely different after taking something specific about problem into account. Like it may turn out that constraints on numbers are very small, or something like that. answered 03 Nov '17, 21:02 7★lebron 3.2k●3●17 accept rate: 25%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,897

question asked: 15 Jul '17, 01:50

question was seen: 577 times

last updated: 03 Nov '17, 21:02