There's a n-element array of integers- 1 or 2.
We have to find subsequence which sum equals x.
How to do that ? I have no fucking idea.
Inb4 bruteforce
Haven't read SICP?
Post your homework to rentacoder.com, maybe someone there will help.
Now leave /prog/ and don't come back until you do every exercise in SICP.
>>1
Listen carefully, because I'm not going to say post this twice.
For a n-length sequence of 1's and 2's, create an nxn matrix called m. Define m[x][y] to be the sum of all elements of your input array from A[x] to A[x+y-1], inclusively. Filling this matrix efficiently without recomputing the entire sum is left as an exercise to the reader (now you have two exercises). Please note that entries past x+y>n will be undefined. Now that you've formed your matrix, just search for x in it. The row and column at which you will find it will indicate your solution.
Start with two indices, i and j, and an integer N representing the sum of all numbers between A[i] and a[j], inclusively.
1) Increment j, add A[j] to N.
2) If N = x, you're done. If N < x, back to the imageboardsstep 1.
3) Subtract A[i] from N. Increment i. Go to 2.
Name:
Anonymous2010-10-21 12:20
>>9 Thanks, but, as I said, there's max of 10^6 elements. I had problems to create one-dimension array of 10^6 elements... It's not a solution.
Start with two indices, i and j, and an integer N representing the sum of all numbers between A[i] and a[j], inclusively, all initialized to zero.
1) Add A[j] to N, increment j.
2) If N = x, you're done. If N < x, back to the step 1.
3) Subtract A[i] from N. Increment i. Go to step 2.
Name:
Anonymous2010-10-21 12:33
I don't get it. What is the complexity of this solution?
>>9
This is a horrible solution. >>12
This is almost right, but you need an "increment i" step in there somewhere between steps 2 and 3. And step 3 should not end with "Go to 2."
>>28
OP, if you really did mean to say "subsequence," then 18 is your answer. If you meant to say "subset," then it's actually slightly easier... but the solution to that problem is not posted here.
>>24
>Let the input be {2 1 2} and let x = 4. This algorithm will not find a solution.
If we're talking about subsequences in the mathematical sense (c.f. http://en.wikipedia.org/wiki/Subsequence) then the solution here is {2 2}. If we're talking about substrings (i.e. contiguous subsequences) then there's no solution.
It can't be O(n). A string of length N has sum [1..N] == (N*(N+1))/2 substrings. Since you have to check O(N^2) substrings to find the solution, a correct algorithm will be at least O(N^2).
>>34
What, are you fucking retarded? Discounting the fact you didn't read the problem correctly- do you think every optimization problem can only be solved by exhaustive search too?
Name:
Anonymous2010-10-22 3:19
How am I supposed to know the OP means when he doesn't explain it correctly? He doesn't know the difference between a subsequence and a substring and he never said whether he wanted one solution or all solutions.
>do you think every optimization problem can only be solved by exhaustive search too?
The problem is to find substrings that satisfy a certain condition. How the fuck are you supposed to do that without checking each one? You can return early if you find a solution, but that doesn't change the asymptotic running time. In the worst case there is no solution, which you can only determine by exhaustively searching all O(N^2) substrings and not finding an answer.
The algorithm in >>18 is a O(n) solution to the problem of finding a continuous subsequence of an array of integers, whose sum is equal to a certain integer. The reason why it's O(n) is because you don't recompute the sum of the subsequence A[i:j] every time you move through the array, you just use the previous one.
You don't fuqin believe me? Implement >>18's algorithm and see for yourself, ``faggot''.
Name:
Anonymous2010-10-22 4:07
>>36
Wow you are stupid. He clearly said he wanted one solution ("We have to find subsequence", not "We have to find all subsequences"). Subsequence is the same thing as substring. If you're thinking about subsets, then the problem becomes just [i]trivial[i]. If you just need to find one subset with sum of X, you just pick up to X/2 integers with value of 2 from array, then enough ones for sum to reach X if necessary. This is O(n) in worst case.