Last Updated: 7 Mar, 2021
Break The Number
Moderate
Asked in companies
Kevin does not like large numbers and so, he decided to break the number ‘N’ in the sum of the ‘Kth’ power of natural numbers. You have to find the number of ways in which Kevin can do so.
For Example:
‘N’ = 30 and ‘K’ = 2
So, the number of ways is 2.
First, 1^2 + 2^2 + 3^2 + 4^2
Second, 1^2 + 2^2 + 5^2
Note:
You cannot use any number two or more times in expressing a number ‘N’. For example, 8 cannot be broken as 2^2 + 2^2.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two space-separated integers ‘N’ and ‘K’ where ‘N’ is the number that Kevin wants to break, and ‘K’ is the number that represents the power to which natural numbers must be raised.
Output Format:
For each test case, print the number of ways Kevin can perform his task described above.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 20
Time limit: 1 sec
Approaches
The basic idea is to go recursively and check whether a particular natural number be part of anyway (in which ‘N’ can be broken).
We are going to use an additional function as:
int helper( int n, int k, int num)Where ‘n’ is the number that Kevin wants to break, ‘k’ is the required power, and ‘num’ is a number that can be a part of broken ‘n’.
There will be two recursive calls at each step, one in which ‘num’ is taken as a part of broken ‘n’ and another in which it is not be taken.
The steps are as follows:
- Inside the “helper” function
- Create a variable named ‘a’ in which store ( ‘n’ - ‘num’^’k’).
- Base conditions are
- If ‘a’ is equal to 0 then return 1.
- If ‘a’ is less than 0 then return 0.
- Return helper(n , k, num + 1) + helper(a, k, num + 1).
- Inside the given function just return the call for “helper” with passing arguments as ‘n’, ‘k’, and 1.
The basic idea of this approach is to first solve the subproblems then reach the main solution and this is done by applying the bottom-up approach of DP.
The steps are as follows:
- Make a dynamic programming table and iterate through from 1 to ‘N’. (say, iterator = ‘i’)
- Now, store the ‘Kth’ power of ‘i’ in some variable say, “val”.
- Iterate again from ‘N’ to ‘i’. (say, iterator ‘j’)
- Check if “val” is less then or equal to ‘j’.
- If true then fill the dp table at ‘j’ by adding the subproblems of ‘N’ equal to ( ‘j’ - “val” ).
- Return the value stored at the nth index in the dp table.
Similar problems