0
$\begingroup$

Given a list of $L$ integers, containing positive and negative number,how do I partition them into $K$ sets such that majority of elements in it are positive. There are two cases in it :

  1. When $K$ is odd.

  2. When $K$ is even.

Now the majority of elements are considered to be positive when more than half of the elements in are positive. For simplicity, the cardinality of each set ($M$) is odd. ($L=K*M$).

Now we can take only the sign of integers i.e. represent positive with $+1$ and negative with $-1$. The elements in the set are to be consecutive so we make our list circular.

Instead of going through every possible consecutive sets, is there a efficient way to make those sets such that atleast $K/2$ are positive sets ?

Eg - 1. $K$ (odd)= $3$

$1 1 1 -1 1 -1 -1 1 -1$

One way : {$2,3.4$}, {$5,6,7$} , {$8,9,1$}

$2$ positive, $1$ negative so majorly positive

  1. $K$ even= $4$

$-1 1 -1 -1 1 1 -1 1 -1 -1 -1 -1$

There is no way possible to it to be major positive.

EDIT : How can we even tell if there is majority of positive sets ?

$\endgroup$
  • $\begingroup$ How do you propose to do this if only one of your integers is positive, and the other $L-1$ are all negative? $\endgroup$ – Gerry Myerson Feb 13 '17 at 10:56
  • $\begingroup$ @GerryMyerson Then we simply it's not possible or rather say it is the list of majority negative sets. $\endgroup$ – Buckster Feb 13 '17 at 10:59
  • $\begingroup$ Work through the list, closing a partition as soon as it has one more positive than negative numbers in it. This gives you the maximum number of predominantly positive partitions. $\endgroup$ – Thumbnail Feb 13 '17 at 11:14
  • $\begingroup$ @Thumbnail I get the idea but every $K$ set has to have exactly $M$ integers in it. Also the way has to be efficient and optimized further. $\endgroup$ – Buckster Feb 13 '17 at 11:19
  • $\begingroup$ I misunderstood the question. $\endgroup$ – Thumbnail Feb 13 '17 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.