Click here to Skip to main content
15,868,164 members
Please Sign up or sign in to vote.
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
Comments
jeron1 5-Apr-18 9:58am    
You have not asked a question.

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.
 
Share this answer
 
Comments
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.
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...
 
Share this answer
 
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.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900