Find the number of non-overlapping pairs that appear in a positive integer array using recursion

Question

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 5-Apr-18 3:48am

Member 13764324

Updated 5-Apr-18 14:58pm

Rick York

v2

Add a Solution

Comments

jeron1 5-Apr-18 9:58am

You have not asked a question.

3 solutions

Add a Solution

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

Jochen Arndt · Answer 1 · 2018-04-05T04:35:00

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.

OriginalGriff · Answer 2 · 2018-04-05T04:36:00

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...

Patrice T · Answer 3 · 2018-04-05T15:00:00

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.

Find the number of non-overlapping pairs that appear in a positive integer array using recursion

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Find the number of non-overlapping pairs that appear in a positive integer array using recursion

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us