@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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
