Click here to Skip to main content
14,028,549 members
Rate this:
 
Please Sign up or sign in to 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:

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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

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:
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.
   
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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

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...
   
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 3

Your code is nicely recursive, but wrong in many ways.
All pairs found in recursion are getting lost:
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.
   

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web01 | 2.8.190419.4 | Last Updated 5 Apr 2018
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100