Efficient way to find number of sums possible

Question

Given three integers n, k and d, how many ways can n be represented as sum of positive integers i<=k, such that d occurs at least once in the sum. It is guarenteed that 0<d<=k. My approach was a recursive one;

#include <stdio.h>
#include <stdlib.h>
int n,k,d,ans=0;
void solve(int totw,int flag)//totw is the total sum till now, and flag is to keep track of the number of d's in the sum.
{
    if(totw>n)
        return;
    if(totw==n && flag>0)//flag>0--->at least 1 d
    {
        ans = (ans+1)%1000000007;//answer is expected modulo 10^9+7
        return;
    }
    int i=1,h=k;
    if(h>n-totw)
        h=n-totw;
    while(i<=h)
    {
        if(i==d)
            flag++;
        solve(totw+i,flag);
        i++;
    }
}
int main()
{
    scanf("%d %d %d",&n,&k,&d);
    solve(0,0);
    printf("%d",ans);
}

Input:
3 3 2
Output:
2
But the judge shows Time Limit Exceeded. Is there any more efficient algorithm to proceed with in this case? 0<n,k<=100
PS:I was just wondering whether there is any combinatoric argument that can solve this question without recursion or iteration. And yes....order of sums matter.

Not sure if I understood correctly but isn't the problem same as computing the number of ways (n-d) can be represented as a sum of i integers where i <= k-1? — Abhishek Bansal, Sep 12 '16 at 15:14
Order for sum matters? if `n==3+5` and `n==5+3` are two different ways, or only one counts? — SergeyS, Sep 12 '16 at 15:14
@AbhishekBansal...I don't think that was the question. Also `d` can occur many times in the sum. — yobro97, Sep 12 '16 at 15:16
@FrankS101...I too think memoization is what I may need here.....could you suggest how it can be implemented here? — yobro97, Sep 12 '16 at 17:39
"Input: 3 3 2 Output: 3" is unclear. Are not only {1,2} and {2,1} the only **2** valid solutions unlike **3** in your example? Looks like your functionality is incorrect as I think it also counts {1,1,1} or {3} as a valid solution. As commented below, get functionality correct and _then_ improve efficiency — chux - Reinstate Monica, Sep 12 '16 at 17:45

md5 · Answer 1 · 2016-09-12T16:52:13.647

You can represent your recursive calls as a graph. Each node is given by the parameters of your function (totw, flag), and you add an edge whenever you make a recursive call. There are about n*2 nodes and n*2*k edges in this graph.

This graph has a very interesting property: it is a DAG (e.g. because totw is strictly increasing at each call). Therefore, when you call solve(totw, flag), you can keep the result in an array, so that you don't compute it twice.

This is actually a way to explain dynamic programming: an algorithm to find the shortest path in a DAG (with slight modifications it can also compute the longest path/the number of paths, but you get the idea). The time complexity on a graph G = (V, E) will be a O(|V|+|E|) (that's actually a kind of amortized analysis).

Thus, keeping the results in an array will result in a O(nk) time complexity.

Actually you can make the implementation even shorter by changing slightly the graph:

enum { UNKNOWN = -1 };

/* not tested */
/* solve(num, d_seen): returns the answer to the problem with a sum
   target, knowing whether `d` was already used */
int solve(int sum, int d_seen)
{
  if (sum == 0) return d_seen;
  int ans = dp[sum][d_seen];
  if (ans == UNKNOWN) {
    ans = 0;
    /* min(a, b) being what it is supposed to be */
    for (int i = 1; i <= min(sum, k); ++i)
      ans = (ans + solve(sum - i, d_seen || (i == d))) % MOD;
  }

  return (dp[sum][d_seen] = ans);
}

By the way you don't put flag back to 0 after incrementing it.

score 0 · Answer 2 · edited May 23 '17 at 10:29

0

Referring to this Wikipedia page: Stars and Bars

Basically the number of ways to split a number n into k positive integers is (n-1)C(k-1) or n-1 choose k-1. Thus, you can iterate for k = 1 to n-d-1 to find the number of ways you can split n-d-1 into any number of positive integers.

Refer here to find out how to efficiently calculate nCk for large n and k efficiently

edited May 23 '17 at 10:29

Community

1
1

answered Sep 12 '16 at 15:47

Benson Lin

1,394
13
17

chux - Reinstate Monica · Answer 3 · 2016-09-12T16:56:53.657

0

Certainly some combinatoric math can solve this without even using code. But the recursive challenge looked fun to try to code.

A lightly tested, example - not much more efficient than OP's.
(Step 1, use more meaningful variable names)

unsigned long solve(unsigned sum_n, unsigned max_value_k, unsigned special_d) {
  if (sum_n == 0) return special_d == 0;
  unsigned long solutions = 0;

  // Improve efficiency, only loop up to min(k,n)
  if (max_value_k > sum_n) {
    max_value_k = sum_n;
  }

  // Will the loop contain d?
  if (max_value_k >= special_d) {
    for (unsigned i = 1; i <= max_value_k; i++) {
      solutions += solve(sum_n - i, max_value_k,
          i == special_d ? 0 : special_d);
      solutions %= 1000000007;
    }
  }
  return solutions;
}

#include <stdio.h>
int main(void) {
  unsigned n, k, d;
  for (n=0; n<100; n++) {
    printf("%u %lu\n", n, solve(n, 100, 1));
    fflush(stdout);
  }
  scanf("%u %u %u", &n, &k, &d);
  printf("%lu\n", solve(n, k, d));
}

edited Sep 12 '16 at 16:56

answered Sep 12 '16 at 16:32

chux - Reinstate Monica

143,097
13
135
256

I don't think it's efficient enough (e.g. `n = k = 100, d = 5`). – md5 Sep 12 '16 at 17:06
@md5 Agree, hence the "not much more efficient than OP's.". As OP has yet to post some test cases, this answer is useful to compare to a candidate faster answer for functionality - hopefully this one is correct. No point in a fast method if it is not functionally correct. – chux - Reinstate Monica Sep 12 '16 at 17:15
@chux...sorry for the late reply.....I have added some example test cases. – yobro97 Sep 12 '16 at 17:35

Efficient way to find number of sums possible

3 Answers3