0

Given series of integers having relation where a number is equal to sum of previous 2 numbers and starting integer is 1

Series ->1,2,3,5,8,13,21,34,55

find the number of ways such that sum of k elements equal to p.We can use an element any number of times.

p=8

k=4.

So,number of ways would be 4.Those are,

1,1,1,5

1,1,3,3

1,2,2,3

2,2,2,2

I am able to sove this question through recursion.I sense dynamic programming here but i am not getting how to do it.Can it be done in much lesser time???

EDIT I forgot to mention that the sequence of the numbers does not matter and will be counted once. for ex=3->(1,2)and(2,1).here number of ways would be 1 only.

warrior
  • 29
  • 5

3 Answers3

0

EDIT: Poster has changed the original problem since this was posted. My algorithm still works, but maybe can be improved upon. Original problem had n arbitrary input numbers (he has now modified it to be a Fibonacci series). To apply my algorithm to the modified post, truncate the series by taking only elements less than p (assume there are n of them).

Here's an n^(k/2) algorithm. (n is the number of elements in the series)

Use a table of length p, such that table[i] contains all combinations of k/2 elements that sum to i. For example, in the example data that you provided, table[4] contains {1,3} and {2,2}.

EDIT: If the space is prohibitive, this same algorithm can be done with an ordered linked lists, where you only store the non-empty table entries. The linked list has to be both directions: forward and backwards, which makes the final step of the algorithm cleaner.

Once this table is computed, then we get all solutions by combining every table[j] with every table[p-j], whenever both are non-empty.

To get the table, initialize the entire thing to empty. Then:

For i_1 = 0 to n-1:
    For i_2 = i_1 to n-1:
        ...
            For i_k/2 = i_k/2-1 to n-1:
                sum = series[i_1] + ... + series[i_k/2]
                    if sum <= p:
                        store {i_1, i_2, ... , i_k/2 } in table[sum]

This "variable number of loops" looks impossible to implement, but actually it can be done with an array of length k/2 that keeps track of where each i_` is.

Let's go back to your data and see how our table would look:

table[2] = {1,1}
table[3] = {1,2}
table[4] = {1,3} and {2,2}
table[5] = {2,3}
table[6] = {1,5}
table[7] = {2,5}
table[8] = {3,5}

Solutions are found by combining table[2] with table[6], table[3] with table[5], and table[4] with table[4]. Thus, solutions are: {1,1,1,5} {1,2,2,3}, {1,1,3,3}, {2,2,2,2}, {1,3,2,2}.

TheGreatContini
  • 6,429
  • 2
  • 27
  • 37
  • Here p can be as big as 10^9.It won't be possible to make an array of that size. – warrior May 13 '16 at 05:22
  • @warrior: see my edits. My algorithm still handles sizes that big without blowing up. – TheGreatContini May 13 '16 at 05:39
  • As it's an online judge problem memory won't be sufficient for your algorithm – warrior May 13 '16 at 06:21
  • @warrior, do you agree that the memory requirements are order n^(k/2) if you use linked lists? Are you saying this is too much? I'm going to say right now that this will use less than any dynamic programming solution. – TheGreatContini May 13 '16 at 06:30
0

You can use dynamic programming. Let C(p, k) be the number of ways that sum k element equal to p and a be the array of elements. Then 

 C(p, k) = C(p - a[0], k - 1) + C(p - a[1], k - 1) + .... + C(p - a[n-1], k - 1)

Then, you can use memorization to speed up your code.

mort
  • 12,988
  • 14
  • 52
  • 97
invisal
  • 11,075
  • 4
  • 33
  • 54
  • Yes i know this.But as p can be upto 10^9 this solution doesn't seem efficient.Can we speed this up.Can we make use of the series given or maximum value of k=10. – warrior May 13 '16 at 06:31
  • 1
    @warrior, it is efficient because the most important thing is not how big is p. It is about how big is k. k will determine the depth of the recursive. Since k is only below 10. – invisal May 13 '16 at 06:35
  • @invisal could you please include the run time analysis in your post? – TheGreatContini May 13 '16 at 06:36
  • @TheGreatContini, it is n^k without memorization. – invisal May 13 '16 at 06:40
  • @invisal I forgot to mention that the sequence of the numbers does not matter and will be counted once. for ex=3->(1,2)and(2,1).here number of ways would be 1 only.Can you tell me what to change in this recursive formula to handle this case. – warrior May 14 '16 at 03:52
0

Hint:

Your problem is well-known. It is the sum set problem, a variation of knapsack problem. Check this pretty good explanation. sum-set problem

Jonathan Prieto-Cubides
  • 2,577
  • 2
  • 18
  • 17