So I was thinking about the election and I was wondering if you had N numbers, what type of algorithm would best be able to tell you if a tie is possible? I know that the sum being divisible by an even number doesn't necessarily mean there is a way to tie. This was inspired by thinking of the up coming election. You can assume all numbers in N are positive and that there may be numbers repeated, think electoral college as an example.
Ask HN: With N numbers, determine if a tie is possible?
1–4 of 4 posts
Re: Ask HN: With N numbers, determine if a tie is possible?
#2This is the partition problem[1]. So to answer your question: the problem is NP-complete, but there are pseudo-polynomial time dynamic programming solutions (see the wikipedia entry for details).
Re: Ask HN: With N numbers, determine if a tie is possible?
#3Off the top of my head:
1. sum all the numbers
2. if the sum is odd, then return false
3. else determine if any set of numbers adds to half the sum
1. choose a number and add it to the set
2. if the sum of the set is less than the number, add another number to the set
3. else remove a number from the set
Re: Ask HN: With N numbers, determine if a tie is possible?
#4Off the top of my head: 1. sum all the numbers 2. if the sum is odd, then return false 3. else determine if any set of numbers adds to half the sum To determine if any set of numbers adds to half the sum: 1. choose a number and add it to the set 2. if the sum of the set is less than the number, add another number to the set 3. else remove a number from the set which numbers to add and remove can be done via brute for…
[deleted]