15,996,462 members
1.00/5 (1 vote)
See more:
For example:
{11, 5, 7, 9, 11, 3, 5} has a total of 2 pairs: 1 pair of 11 and 1 pair of 5
{11, 5, 7, 9, 11, 11} has a total of 1 pair: a pair of 11
{11, 5, 7, 9, 11, 3, 11, 5, 11} has a total 3 pairs: 2 pairs of 11 and 1 pair of 5

Write a recursive function findpair. This function takes 3 arguments: the positive integer array, the start index of the array and the end index of the array. It returns the total count of pairs found in this array. If no pair is found, this function should return 0. During the search process, you are allowed to modify elements in the array.

What I have tried:

C++
```int findpair(int array[], int start, int end)
{
int pairs = 0;

if(end<=start)
{
return 0;
}

if(array[start]==array[end])
{
pairs++:
}

findpair(array, start+1, end);
findpair(array, start, end-1);

return pairs;
}```
Posted
Updated 5-Apr-18 14:58pm
v2
jeron1 5-Apr-18 9:58am
You have not asked a question.

## Solution 1

This is a homework / assignment question. So you will not get a complete solution here.

But I have two tips:

1. A recursive function will not "see" the local variables of the caller. If you have to sum up a value, you have to use the return value:
C++
```int rec_func(some_param)
{
int result = 0;
if (not_end_condition(some_param))
result += rec_func(some_modified_param);
return result;
}```

2. The trick is to find a method to perform the task. Here only full pairs should be counted (a triple is counted as one pair) and you have to ensure that both numbers of a counted pair are not used again. This is quite simple here due to two statements from the assignment: "positive integer array" and "you are allowed to modify elements in the array".

Now think about the above and how it can be done.

Member 13764324 5-Apr-18 12:01pm
It's not the homework. It's just practice question for midterm. But there is no answer provided for practice question..Could u give me complete solution please?
Jochen Arndt 5-Apr-18 13:37pm
It would be no practice if you got a solution written by others.

There is also not a single solution.

## Solution 2

Think about how you would do it manually. I'd start with the first element in the array, and then search for it's match. If I found it, I'd remove the second one from the array. If I didn't, I'd remove the element from the array.
Then search again from the next element, if any.

At the end, the number of pairs is the number of remaining elements.
```| Start
V
11, 5, 7, 9, 11, 3, 5  - match: remove.
| Start
V
11, 5, 7, 9, 3, 5  - match - remove
| Start
V
11, 5, 7, 9, 3  - no match - remove
| Start
V
11, 5, 9, 3  - no match - remove
| Start
V
11, 5, 3  - no match - remove
| Start
V
11, 5  - no more elements : 2 matches.```

Hint: The easiest way to remove an element is to overwrite it with the last one, and reduce the count by one...

## Solution 3

Your code is nicely recursive, but wrong in many ways.
All pairs found in recursion are getting lost:
C++
```int findpair(int array[], int start, int end)
{
int pairs = 0;

if(end<=start)
{
return 0;
}

if(array[start]==array[end])
{
pairs++:
}

findpair(array, start+1, end); // all pairs found here are lost
findpair(array, start, end-1); // all pairs found here are lost

return pairs;
}```

Once you repaired the first problem, you will gall in second one, pairs will be counted more than once:
This array {5, 5, 5, 5} is 2 pairs, but your code will find much more.
The key is in
Quote:
During the search process, you are allowed to modify elements in the array.

you have to change the array in order to prevent counting an element in more than 1 pair.
Finding the correct algorithm is your homework.