The Power Sum, a recursive problem by HackerRank
Another one by HackerRank: https://www.hackerrank.com/challenges/the-power-sum:
Solution is a recursive one where we're varying the number being tested, always ensuring to increment it after adding it up to the current sum, and using as a halting criteria when the current sum surpasses the target sum. Code is down below, cheers, Marcelo.
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(String[] args)
{
int x = Int32.Parse(Console.ReadLine());
int n = Int32.Parse(Console.ReadLine());
int solutions = 0;
Process(0, x, 1, n, ref solutions);
Console.WriteLine(solutions);
}
static void Process(int currentSum, int targetSum, int currentNumber, int n, ref int solutions)
{
if (currentSum == targetSum)
{
solutions++;
return;
}
for (int i = currentNumber; currentSum + (int)Math.Pow(i, n) <= targetSum; i++)
Process(currentSum + (int)Math.Pow(i, n), targetSum, i + 1, n, ref solutions);
}
}
Find the number of ways that a given integer, , can be expressed as the sum of the power of unique, natural numbers.
Input Format
The first line contains an integer .
The second line contains an integer .
The second line contains an integer .
Constraints
Output Format
Output a single integer, the answer to the problem explained above.
Sample Input 0
10
2
Sample Output 0
1
Explanation 0
If and , we need to find the number of ways that can be represented as the sum of squares of unique numbers.
This is the only way in which can be expressed as the sum of unique squares.
Sample Input 1
100
2
Sample Output 1
3
Explanation 1
Sample Input 2
100
3
Sample Output 2
1
Explanation 2
can be expressed as the sum of the cubes of .
. There is no other way to express as the sum of cubes.
. There is no other way to express as the sum of cubes.
Solution is a recursive one where we're varying the number being tested, always ensuring to increment it after adding it up to the current sum, and using as a halting criteria when the current sum surpasses the target sum. Code is down below, cheers, Marcelo.
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void Main(String[] args)
{
int x = Int32.Parse(Console.ReadLine());
int n = Int32.Parse(Console.ReadLine());
int solutions = 0;
Process(0, x, 1, n, ref solutions);
Console.WriteLine(solutions);
}
static void Process(int currentSum, int targetSum, int currentNumber, int n, ref int solutions)
{
if (currentSum == targetSum)
{
solutions++;
return;
}
for (int i = currentNumber; currentSum + (int)Math.Pow(i, n) <= targetSum; i++)
Process(currentSum + (int)Math.Pow(i, n), targetSum, i + 1, n, ref solutions);
}
}
Very nice Marcelo! Just discovered your blog thanks Tony interview about Quicksort! Added to my Feedly!
ReplyDeletevery neat, Marcelo! My solution is almost identical :)
ReplyDeletehttp://ideone.com/gxDICb
#include
#include
using namespace std;
int number_of_ways(int target, int power, int start) {
if (target == 0) return 1;
int total = 0;
for (int j = start + 1; pow(j, power) <= target; ++j) {
total += number_of_ways(target-pow(j, power), power, j);
}
return total;
}
int main() {
int x, n; cin >> x >> n;
cout << number_of_ways(x, n, 0);
return 0;
}
can u please explain the code
DeleteHi, I have one question.. If you are using recursion,why you have used loop inside function?
ReplyDeleteRecursion is not free, since, unless function is tail-recursive and compiler knows how to optimize it into iterative implementation, a stack has to be maintained. It's better to use recursion only where it feels natural by directly modeling the algorithm, and iterative computations are usually more natural and shorter when written with plain loops.
DeleteYour blog is very nice,Thanks for sharing good blog.
ReplyDeleteซอมบี้
Nice initiative. Keep doing the good work. csmonk
ReplyDelete