The number of whole sections is possible for a range
A task:
You are given two numbers, namely A and S. Write a program to find the number of ways in which numbers that are greater than or equal to S can be added to get the sum of A. Print the result modulo 10 ^ 9 + 9.
eg. If A is 3 and S is 1, then there are three ways to achieve A = 3 using numbers greater than and equal to S = 1. The solutions are <1,1,1>, <1,2> and <3>. For A = 9 and S = 3, the solutions will be <3.3.3 <3.6 <4.5> <9>. There are 4 ways to get 9 using a number greater than 3.
I used below approach.
- Check if there is (S> A / 2), then only one solution is possible. for example, if A = 9 and S = 5, then only one solution is possible, which is <9>.
- If condition 1 is not true and create a list and store all i that are S <= i <= A / 2 in the list.
-
For each number, I'm on the list.
3.1. Although A> = i
3.1.1. Decrease A by i.
3.1.2. If A> = i, then increment count (count stores complete permutations and is initially set to 1).
3.1.3. Else exit the while loop.
This approach has a quadratic time complexity. Is there a better way to solve this problem?
source to share
I was able to solve this using dynamic programming. The problem is similar to the problem with changing coins, where the sum is the total amount and d, d + 1, d + 2, .., sum are the coins available to us to reach the amount. Below is the java code I wrote.
private static int countPartitionsDP(int d, int sum){
if(d>sum/2)
return 1;
if(d>sum)
return 0;
int coins=sum-d+1;
int[][] dp=new int[coins][sum+1];
for(int i=0;i<coins;i++){ //for sum=5 and d=2 number that we use to achieve sum is 2,3,4,5 i.e (i+d).
for(int j=0;j<=sum;j++){
if(j==0) //sum=0 can be achieved in 1 way. dp[i][0]=1
dp[i][j]=1;
else if(i==0){
if(j<(i+d)){ //if current sum j is less than current value of d i.e.(i+d).
dp[i][j]=0;
}else{
dp[i][j]=dp[i][j-i-d]; //if sum is greater than current value of d then dp[i][j]=dp[i][j-d]
}
}else if(j<(i+d)){
dp[i][j]=dp[i-1][j];
}else{
dp[i][j]=dp[i-1][j]+dp[i][j-i-d];
}
}
}
return dp[coins-1][sum];
}
source to share