TCAZN
- 1
- 0
Hi all,
I was just looking at the U.S. electoral map, and I was wondering if there could possibly be a tie in presidential elections (the answer is probably no). I tried to think of an efficient algorithm to answer this question, but due to my limited intelligence and imagination, all I could think of is the brute force method. I guess in this particular problem, efficiency probably does not matter since the number of states definitely doesn't follow any kind of Moore's Law.
Anyways, I was just wondering if anyone knows an efficient algorithm for the following problem:
Given a finite sequence $$a_1, a_2, \dots a_n,$$ determine whether there is a sub-sequence $$a_{i_1}, a_{i_2}, \dots a_{i_k}$$ such that $$\sum_{j=1}^{k} a_{i_j} = \frac{1}{2} \sum_{j=1}^{n}a_j$$.
I was just looking at the U.S. electoral map, and I was wondering if there could possibly be a tie in presidential elections (the answer is probably no). I tried to think of an efficient algorithm to answer this question, but due to my limited intelligence and imagination, all I could think of is the brute force method. I guess in this particular problem, efficiency probably does not matter since the number of states definitely doesn't follow any kind of Moore's Law.
Anyways, I was just wondering if anyone knows an efficient algorithm for the following problem:
Given a finite sequence $$a_1, a_2, \dots a_n,$$ determine whether there is a sub-sequence $$a_{i_1}, a_{i_2}, \dots a_{i_k}$$ such that $$\sum_{j=1}^{k} a_{i_j} = \frac{1}{2} \sum_{j=1}^{n}a_j$$.