Recursive algorithm implementation in java

Question

I am trying to write a method with the following header:

public static boolean difference(int[] numbers, int size, int difference) {...}

I want it to be able to determine if it is possible to choose any two integers from the list "numbers" such that the difference between them is equal to the parameter "difference".

So far I was thinking that I should create a list where the elements contain all possible combinations of the elements in list "numbers" and then fill another list of all possible difference values.

Then I would finally check if the parameter "difference" is inside that list. If it is then it would return true. I also want to do this recursivly so any help would be appreciated. thanks!

Looks like homework to me meta.stackexchange.com/questions/18242/… is it? — brabster
– brabster, Commented Nov 18, 2012 at 20:54
Your solution is rather inefficient. Try sorting the numbers first. — Tomasz Nurkiewicz
– Tomasz Nurkiewicz, Commented Nov 18, 2012 at 20:55
Why do you want to use recursion? There are some cases in which recursion makes code simpler, but you cannot know you have one of those cases before you know how you are going to solve the problem. — Patricia Shanahan
– Patricia Shanahan, Commented Nov 18, 2012 at 21:03

brabster · Accepted Answer · 2012-11-18 21:32:14Z

1

I'm assuming you're trying to learn about recursion, and I'm assuming this is homework. I won't give you a code example, but I hope this helps you.

Maybe you need to think about how to break your problem up into simpler sub problems. Perhaps instead of the harder problem of finding a pair in the list with a given difference, you could write a method that just checked whether the right difference could be found by taking the number at the start of the list and comparing it to all the other numbers in the list.

Then, maybe you could modify your method so that it pops off the number at the start, checks against the rest of the list, and if unsuccessful calls itself with the rest of the list? Think about what to return. If you get this far you've done it. Watch out for what happens when you run out of elements left in the list.

edited Nov 18, 2012 at 21:32

answered Nov 18, 2012 at 21:07

brabster

43.7k29 gold badges150 silver badges189 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

arshajii · Accepted Answer · 2012-11-18 21:07:09Z

1

There's no need to create an entire list of differences - what if numbers[1] - numbers[0] gives the desired difference? You would have wasted a whole lot of time. You can just use two nested for-loops to loop over the array and check if any two numbers at distinct indexes have the desired difference; if any do, return true and exit the method altogether, since there would be no reason to continue the loop.

edited Nov 18, 2012 at 21:07

answered Nov 18, 2012 at 20:56

arshajii

130k26 gold badges246 silver badges293 bronze badges

Collectives™ on Stack Overflow

Recursive algorithm implementation in java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related