C++ Problem

[JonathanVP]

I am taking a C++ refresher course and I decided to do this assignment for extra credit regarding arrays:

Implement a method:

boolean findPair(int[] array, int sum)

That should return true if there are any two values that add up to "sum". So for instance if I passed in (0, 3, -1, 6) as the array, then it would return true if sum was 9 or 2, but false for 100 or 8.

If there are 4 members in this array, then I believe I have to do a loop 24 times or 4! to add up to the sum?

[Andareed]

You should only have to loop about n^2 times (not n!).

[jon419]

I wouldn't go through the loop all the times required, just exit the loop if your sum is found.

So, compare the first element to all the elements. Match? Yes, exit (return true). No, compare the next element to all elements. Match? Yes, exit (return true). No....and so on.

for(int i=0;i<length;i++) {
	for(int j=0;j<lenth;j++) {
		if(j != i) {
			 if((sum == array[i] + array[j]) {
					  return true;
			 }
		 }
	 }
}
return false;

--That code is probably no where near perfect, but the gist of it should work. I think...half the time i code stuff that never works, so don't listen to me.

In this case, each outter loop 4 times and for each outter loop, each inner loop 4 times. That would be a total of 20.

Outter

Inner

Inner

Inner

Inner

Outter

Inner

Inner

Inner

Inner

Outter

Inner

Inner

Inner

Inner

Outter

Inner

Inner

Inner

Inner

[sharpenyourteeth]

  jon419 said:

for(int i=0;i<length;i++) {
	for(int j=0;j<lenth;j++) {
		if(j != i) {
			 if((sum == array[i] + array[j]) {
					  return true;
			 }
		 }
	 }
}
return false;

I belive you're doing some extra work there. With the numbers the OP used, the first iteration of the outter loop you'd add:

0+3, 0+(-1), 0+6

then on the next iteration of the outter loop you'd add

3+0, 3+(-1), 3+6

you just calculated 0+3 twice.

instead of starting the inner loop at 0, start it at j=i+1.

  jon419 said:

half the time i code stuff that never works, so don't listen to me.

same goes with me, i didnt test this so it might no be right :D

[AndreasV]

Special case of the subset-sum problem, which is NP-Complete (doesn't mean this special case of 2 integers-to-sum is NPC, or NP for the matter.

[mukul]

U REQUIRE nC2 TRIALS..... AS MOST EFFICINT PROGRAM..........