@Anurag... 'SuperSum' can be reduced to the following form..
SuperSum ( k, n) = SuperSum (k-1, n) * (n+k) / (k+1) .. Time Complexity : O(K) , Space Complexity : O(1) Code: int getSuperSum(int k, int n) { int superSum = n; // SuperSum(0, n) int i = 0; while( ++i <= k) { superSum = ( superSum * ( ( n + k )%1000000007 ) ) / (k+1); superSum %= 1000000007; } return superSum; } On Jan 3, 12:08 pm, Anurag Gupta <anurag.gupta...@gmail.com> wrote: > SuperSum is a function defined as: > * SuperSum(0 , n) = n, for all positive n. > * SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + > SuperSum(k-1 , n), for all positive k, n. > > Given k and n, return the value for SuperSum(k , n) modulo 1000000007. > 1<=k<=50 > 1<=n<=1,000,000,000 > For Example: SuperSum(1,3) = 6 > SuperSum(2,3) = 10 > SuperSum(4,10) = 2002 > SuperSum(10,35) = 150595840 > > I thought of constructing a table dp [50][200000] and pre-computing > these values but the solution will definitely time out > as n can be upto 10^9. > Please suggest how to approach this problem (and more importantly such > problems)? > Thank You -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.