C++

Forum

 
Function comparison

Oriol Serrabassa (100)
Write a function
int common_elements (const vector <int> &X, const vector <int> &Y)

that given two vectors X and Y which are in strictly increasing order, returns the number of common elements in the two vectors, that is, the number of integer numbers a such that a=X[i]=Y[j] for any i and j.


I made myself 2 versions of the functions: one that always works and one that doesn't always work:

Always work:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int common_elements (const vector <int> &X, const vector <int> &Y) {
        int counter = 0;
	for (int i = 0, j = 0; i < X.size() and j < Y.size();) {
                if (X[i] == Y[j]) {
                        ++counter;
                        ++i;
                        ++j;
                }
                else 	if (X[i] > Y[j]) ++j;
                	else 	if (X[i] < Y[j]) ++i;
        }
        return counter;
}


What is special about this function is that the loop doesn't automatically increases the variable created before the loop condition, so we do not know how many loops the for will do but doing it this way grants the less number of loops (probably).


Doesn't always work:
1
2
3
4
5
6
7
8
9
 
int common_elements (const vector <int> &X, const vector <int> &Y) {
	int counter = 0;
	for (int i = 0; i < X.size(); ++i) {
		for (int j = 0; j < Y.size(); ++j) {
			if (X[i] == Y[j]) ++counter;
		}
	}
	return counter;
}


This one checks for every integer of X all the integers of Y, makes more loops than the previous function and it is obviously less eficient.

My question is simple: How can the second function give wrong outputs in some cases?
Last edited on
jlb (4973)
What makes you think that the second function is wrong, not the first?

Please show your sample input, the output (from both functions) and the expected output with that supplied input. Be sure to provide input data that works as expected and input data that fails expectations (a small complete program that we can compile would be helpful as well).





Last edited on
Oriol Serrabassa (100)
My programs are checked via an online marking system and program was accepted using first function meanwhile using the second function gave a wrong answer. There are no public inputs.

Here is the program I tested my functions with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include <vector>
using namespace std;

int common_elements (const vector <int> &X, const vector <int> &Y) {
	// function code here
}

int main () {
    	int n, m;
    	while (cin >> m >> n) {
		vector <int> X (m);
		for (int i = 0; i < m; ++i) cin >> X[i];
		vector <int> Y (n);
		for (int i = 0; i < n; ++i) cin >> Y[i];
        	cout << common_elements (X,Y) << endl;
    	}
}


Not a while ago, I discovered that if I use inputs that contain the same number repeated in both vectors outputs differ. I didn't think this would be the case since problem stated that vector is in strictly increasing order so I thought the vectors wouldn't hold repeated numbers.
An input that illustrates this is the following:

4 3
2 2 2 2
2 2 2

Output first function = 3
Output second function = 12

Guess my problem was a misunderstanding in reading the problem. I will look the code a bit more or if anyone knows another case where second functons fails, please write it down.
dhayden (5795)
strictly increasing order

This seems to imply that the vectors contain unique value only - no duplicates within the vector. If they can contain duplicates then you'll get different answers - both wrong :)

Input (-1 terminates the vector):
1 2 3 4 5 6 8 8 9 10 11 15 16 20 22 -1
1 5 7 8 8 12 14 15 19 20 21 22 -1

Output:
first version: 7
second version: 9


The correct answer is 6: the common elements are 1, 5, 8, 15, 20 and 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include<iostream>
#include <vector>

using namespace std;

int common1 (const vector <int> &X, const vector <int> &Y) {
        int counter = 0;
	for (size_t i = 0, j = 0; i < X.size() and j < Y.size();) {
                if (X[i] == Y[j]) {
                        ++counter;
                        ++i;
                        ++j;
                }
                else 	if (X[i] > Y[j]) ++j;
                	else 	if (X[i] < Y[j]) ++i;
        }
        return counter;
}

int common2 (const vector <int> &X, const vector <int> &Y) {
	int counter = 0;
	for (size_t i = 0; i < X.size(); ++i) {
		for (size_t j = 0; j < Y.size(); ++j) {
			if (X[i] == Y[j]) ++counter;
		}
	}
	return counter;
}

main()
{
    vector<int> v1, v2;
    int num;

    while (cin >> num) {
	if (num == -1) break;
	v1.push_back(num);
    }
    while (cin >> num) {
	if (num == -1) break;
	v2.push_back(num);
    }

    cout << "first version: " << common1(v1, v2) << '\n';
    cout << "second version: " << common2(v1, v2) << '\n';
    return 0;
}

jlb (4973)
With that input is clear that the first snippet will be limited by the size of the smallest vector.
i < X.size() and j < Y.size()
Since all the values are equal this is really what the first snippet looks like:
1
2
3
4
5
6
7
8
9
10
11
12
 
int common_elements(const std::vector<int> &X, const std::vector<int> &Y)
{
    int counter = 0;
    int value = std::min(X.size(), Y.size());

    for(counter = 0; counter < value; counter++)
    {

    }

    return counter;
}


The second snippet will run X * Y times.
Again since the values are all equal you end up with:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int common_elements1(const std::vector <int> &X, const std::vector <int> &Y)
{
    int counter = 0;

    for(size_t i = 0; i < X.size(); ++i)
    {
        for(size_t j = 0; j < Y.size(); ++j)
        {
                ++counter;
        }
    }

    return counter;
}



Last edited on
Oriol Serrabassa (100)
@dhayden Thanks for clarifying that but since you have 8 repeated twice, shouldn't the common elements be 7 since 8 is counted twice? This proves that what I said about repeated numbers might be true.

@jlb If you are trying to say something, I don't get it.

I have no clue at all of where the second function it might fail.
If you analyze the code there shouldn't be any error. Even thought I know I am making unnecessary loops (like if the vector wasn't ordered) the program checks all elements of the vector Y for each element of the vector X. So we know that the second function is inefficient but errorproof.

So how does that lead to output a different result than the first functions knowing that they exactly do the same thing but differently assuming there are no repeated numbers?

My guess is that they made a mistake in writing that the vectors are in strictly increasing order instead of increasing order unless someone can prove otherwise
Last edited on
jlb (4973)
If you analyze the code there shouldn't be any error.

There is no compile error, but there is a logic error in your second snippet.

Even thought I know I am making unnecessary loops (like if the vector wasn't ordered) the program checks all elements of the vector Y for each element of the vector X.

Yes, exactly. And since every element is equal you will increment the counter every time through the loop. Which means you will get a value for your counter of X * Y, or 12 in this case.

So how does that lead to output a different result than the first functions knowing that they exactly do the same thing

No the two snippets are not doing exactly the same thing. If they were doing exactly the same thing then they would give the exact same output.

My guess is that they made a mistake in writing that the vectors are in strictly increasing order instead of increasing order unless someone can prove otherwise

No, I think you're misunderstanding what they're saying. I believe that @dhayden has the correct idea. Both vectors will be sorted in increasing order and there will be no duplicates in either vector. You can't have "strictly increasing order" if you have duplicates, because when you have a duplicate you don't have an increasing order.

Oriol Serrabassa (100)
@jlb But if we assume the vector are in strictly increasing order there is no fear in checking all elements since we know there will be only one element or none in Y that Y[j] == X[i]. However if the vector aren't in strictly increasing order there can be more than one value that Y[j] == X[i] so that's where my second function fails. It has to be because vectors aren't in strictly increasing order or you can just give an input where the second functions fails and we end this faster.
Last edited on
lastchance (6980)
One more for your blind-testing collection, @Oriol Serrabassa!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <iostream>
#include <vector>
#include <set>
using namespace std;


int common1( const vector<int> &X, const vector<int> &Y) {
   int counter = 0;
   int loops = 0;
   for ( size_t i = 0, j = 0; i < X.size() and j < Y.size(); ) 
   {
      loops++;
      if ( X[i] == Y[j] )
      {
         ++counter;
         ++i;
         ++j;
      }
      else if ( X[i] > Y[j] ) ++j;
      else if ( X[i] < Y[j] ) ++i;
   }
// cout << "   Number of loops by method 1 = " << loops << endl;
   return counter;
}


int common2( const vector<int> &X, const vector<int> &Y )
{
   int counter = 0;
   int loops = 0;
   for ( size_t i = 0; i < X.size(); ++i )
   {
      for ( size_t j = 0; j < Y.size(); ++j )
      {
         loops++;
         if ( X[i] == Y[j] ) ++counter;
      }
   }
// cout << "   Number of loops by method 2 = " << loops << endl;
   return counter;
}


int common3( const vector<int> &X, const vector<int> &Y )
{
   set<int> combined;
   for ( size_t i = 0; i < X.size(); ++i ) combined.insert( X[i] );
   for ( size_t i = 0; i < Y.size(); ++i ) combined.insert( Y[i] );
   return X.size() + Y.size() - combined.size();
}


int main()
{
   int m, n;

   cout << "Enter m and n: ";
   cin >> m >> n;

   cout << "Enter " << m << " elements for X (ASCENDING ORDER, NO DUPLICATES!): ";
   vector<int> X(m);
   for ( int i = 0; i < m; ++i ) cin >> X[i];

   cout << "Enter " << n << " elements for Y (ASCENDING ORDER, NO DUPLICATES!): ";
   vector<int> Y(n);
   for ( int i = 0; i < n; ++i ) cin >> Y[i];

   cout << "\nCommon elements by method 1 = " << common1( X, Y ) << '\n';
   cout << "\nCommon elements by method 2 = " << common2( X, Y ) << '\n';
   cout << "\nCommon elements by method 3 = " << common3( X, Y ) << '\n';
}


Enter m and n: 5 5
Enter 5 elements for X (ASCENDING ORDER, NO DUPLICATES!): 1 3 5 7 9
Enter 5 elements for Y (ASCENDING ORDER, NO DUPLICATES!): 5 7 9 11 13

Common elements by method 1 = 3

Common elements by method 2 = 3

Common elements by method 3 = 3



I can't see why (for strictly increasing vector input) they should be different, I'm afraid.

You could make method 2 slightly more efficient by breaking out of the j loop if a common element is found.
Oriol Serrabassa (100)
I think you are all missing the point.
What I am trying to say is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int common_elements (const vector <int> &X, const vector <int> &Y) {
        int counter = 0;
	for (int i = 0, j = 0; i < X.size() and j < Y.size();) {
                if (X[i] == Y[j]) {
                        ++counter;
                        ++i;
                        ++j;
                }
                else 	if (X[i] > Y[j]) ++j;
                	else 	if (X[i] < Y[j]) ++i;
        }
        return counter;
}

This functions gives correct output when:
- Vector X and Y are in strictly increasing order
- Vector X and Y are in increasing order


1
2
3
4
5
6
7
8
9
 
int common_elements (const vector <int> &X, const vector <int> &Y) {
	int counter = 0;
	for (int i = 0; i < X.size(); ++i) {
		for (int j = 0; j < Y.size(); ++j) {
			if (X[i] == Y[j]) ++counter;
		}
	}
	return counter;
}

This functions gives correct output when:
- Vector X and Y are in strictly increasing order

Am I right or not?
Last edited on
lastchance (6980)
Am I right or not?


Unless the vectors are in strictly increasing order then the problem statement is ambiguous.

Take
X = {1,3,3,5}
Y = {2,3,3,6}

Is that 1 common element (3-3) or 2 common elements (3-3,3-3)? Take whichever definition you like!

The only reasonable problem is one that doesn't allow duplicates, i.e. is strictly increasing.

I don't know where your online marking system is (wish you'd tell us!) but it doesn't supply much feedback! Maybe it has other constraints that it hasn't stated explicitly: some very large vectors, or time constraints (which might fit with the less efficient method 2 failing occasionally - you could try slowing method 1 down by inserting some irrelevant, but time-consuming calculations to test that hypothesis).




Last edited on
Oriol Serrabassa (100)
I am using Jutge.org it is 100% reliable since when you send a problem that should be correct you get an error called "Setter Error":
The solution provided by the problem setter (the problem author) is incorrect. This should normally not happen, and it is not your fault in anyway. Please kindly request the problem author to repair this problem. Please do not contact the Judge maintainers but the problem author him/her-self.

I can say this setter error works properly since I have had cases where I got this error and the problem owner had to fix the solution.

The problem there might be, is that users can create and post their own problems, so that's why I have been insisting that the owner of the problem made a writing mistake in saying strictly increasing

I have done approximately 300 problems done there and this is the first time it has happened so the chance of the writing mistake is highly possible.

About this:

Take
X = {1,3,3,5}
Y = {2,3,3,6}

Is that 1 common element (3-3) or 2 common elements (3-3,3-3)? Take whichever definition you like!


Since my problem has been accepted with this function whatever this outputs is correct
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int common_elements (const vector <int> &X, const vector <int> &Y) {
    int counter = 0;
	for (int i = 0, j = 0; i < X.size() and j < Y.size();) {
                if (X[i] == Y[j]) {
                        ++counter;
                        ++i;
                        ++j;
                }
                else 	if (X[i] > Y[j]) ++j;
                	else 	if (X[i] < Y[j]) ++i;
        }
        return counter;
}


With the input you said, it outputs a 2 and it totally makes sense. If you wonder why, let's just review what the problem states:

Returns the number of common elements in the two vectors, that is, the number of integer numbers a such that a=X[i]=Y[j] for any i and j.
Last edited on
lastchance (6980)
No, it doesn't make sense to use this example with duplicates. Your function gives 2 values of a (which are both the same value, i.e 3). But how many different values of a is this? Just 1.
Oriol Serrabassa (100)
The problem is asking how many common elements there are in the two vectors, not how many common numbers there are in the two vectors.

Even if 3 appears twice in each vector in your example, you should output 2 since there are 2 common elements in the vector even if they are the same number. If the problem asked you how many common numbers there are in the two vectors the answer would be 1, but it doesn't.

Anyway, I am closing the post.
Topic archived. No new replies allowed.