2009-01-20, 09:58 PM
(This post was last modified: 2009-01-21, 02:04 AM by KajitiSouls.)
Are all the integers in set X explicitly/assumed to be sorted in ascending order?
What I'm about to say assumes the above is true.
1.) If I'm understanding this correctly, you're adding the sum of the numbers in indexes [i-j] (i through j inclusive), where the sum of the numbers in indexes [i-(j-1)] < Sum(X) / 2, and seeing if this is over Sum(X) / 2.
Counter-proof: X = { 1, 5, 5, 7, 7, 15, 30 }
2.) You're adding the sum of the numbers in indexes [i-j], where j - i = over half the elements in set X, and you're checking if the sum of the numbers in indexes [i-j] are higher than Sum(X) / 2.
Counter-proof: X = { a, a }
(yeah that was lame xD)
With the initial assumption, it seems you only really need to check one solution.
What I'm about to say assumes the above is true.
Devil's Sunrise Wrote:Next step here would then be to check if i numbers equal to half the sum of X, starting from 1, incrementing by 1 until i is over half of the amount of numbers in X. While we do this, we check if all the solutions are over half the sum of X (if it is, then sorry, no solution).Two interpretations...
1.) If I'm understanding this correctly, you're adding the sum of the numbers in indexes [i-j] (i through j inclusive), where the sum of the numbers in indexes [i-(j-1)] < Sum(X) / 2, and seeing if this is over Sum(X) / 2.
Counter-proof: X = { 1, 5, 5, 7, 7, 15, 30 }
2.) You're adding the sum of the numbers in indexes [i-j], where j - i = over half the elements in set X, and you're checking if the sum of the numbers in indexes [i-j] are higher than Sum(X) / 2.
Counter-proof: X = { a, a }
(yeah that was lame xD)
With the initial assumption, it seems you only really need to check one solution.