Break The Number

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
5 upvotes
Asked in companies
Deutsche BankAdobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
30 2
3 1
Sample Output 1:
2
2
Explanation For Sample Input 1:
For the first test case, the explanation is given above.

In the second test case, the required number of ways are 1^1+ 2^1 and 3^1.
Sample Input 2:
3
100 3
1 4
5 5
Sample Output 2:
1
1
0
Hint

Can you think of solving through all the subproblems?

Approaches (2)
Recursion

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.
Time Complexity

O(2^(Nth root of K) * log(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.

 

Since we are doing two recursive calls at each step and the height of the recursion tree goes up to the ‘Nth’ root of ‘K’ and so, it takes time as O(2^(Nth root of K)) but along with this, we are also using power function which takes O(log(K)) time and, so the overall time complexity will be O(2^(Nth root of K) * log(K)).

Space Complexity

O(Nth root of 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.

 

Since the height of the recursion tree goes up to the ‘Nth’ root of ‘K’ in the worst case and so, the overall space complexity will be O(Nth root of K).

Code Solution
(100% EXP penalty)
Break The Number
Full screen
Console