Problem Statement:
You are given two numbers, namely A and S. Write a program to find the number of ways in which the numbers that are greater than or equal to S can be added to get the sum A. Print the result as modulo 10^9+9.
e.g. If A is 3 and S is 1 then there are three ways to achieve A=3 using numbers greater and equal to S=1. Solutions are <1,1,1>, <1,2> and <3>. For A=9 and S=3 the solutions would be <3,3,3>, <3,6>, <4,5> and <9>. Total 4 ways to get 9 using number greater than equal to 3.
I have used below approach.
- Check if (S>A/2) then there is only one solution possible. e.g if A=9 and S=5 then only one solution is possible that 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 in the list.
3.1. While A>=i
3.1.1. Decrement A by i.
3.1.2. If A>=i then increment count(count stores the total permutations and is initially set as 1).
3.1.3. Else come out of while loop.
This approach has quadratic time complexity. Is there a better way to solve this?