You are not logged in. Please login at www.codechef.com to post your questions!

×

BackTracking - The power Sum(HackerRank's problem) Recursion

Hello everyone,

I was trying to solve this Power sum problem but wasn't able to solve it. I tried reading the editorial but couldn't get it.

1) I'm not sure what backtracking is and how it works?

2) Can you please discuss your approach?

Thank you

asked 23 Dec '17, 11:35

kunnu120's gravatar image

2★kunnu120
5189
accept rate: 5%


Well, Your problem had two solutions, one recursive(slower) and one dp solution.

Recursive Solution: sum(X, N, 1) gives the answer.

static int sum(int X, int N, int num){

int value = X - (int)Math.pow(num, N);

if(value < 0)return 0;

if(value == 0)return 1;

return sum(X, N, num+1) + sum(value,N,num+1);

}

Refer DP solution here, though try forming dp solution from above recursive one first!!.

link

answered 23 Dec '17, 18:24

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

Thanks but can you please tell me how

return sum(X, N, num+1) + sum(value,N,num+1);

this works

(24 Dec '17, 08:29) kunnu1202★

Sum(X,N,num+1) gives number of ways, X can be formed using nth power of numbers greater than num, without including nTh power of num.

Sum(value, N,num+1) gives the same, while including Nth power of num.

(24 Dec '17, 17:29) taran_14076★

If you wanna read about Backtracking, read here and here and try to solve the Famous N-queen problem.

I will soon share the solution for Your problem, probably tonight because i'm running busy at the moment.

link

answered 23 Dec '17, 12:14

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

Thank you I'll wait for your solution :)

(23 Dec '17, 13:19) kunnu1202★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×348
×310
×104

question asked: 23 Dec '17, 11:35

question was seen: 1,688 times

last updated: 24 Dec '17, 17:29