You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

chan55555's gravatar image

3★chan55555
214
accept rate: 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.

link

answered 03 Nov '17, 21:02

lebron's gravatar image

7★lebron
2.8k316
accept rate: 26%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,671

question asked: 15 Jul '17, 01:50

question was seen: 482 times

last updated: 03 Nov '17, 21:02