Quote:
I am not sure what "two comparisons" means here.
using namespace std;
int FindDuplicate(vector<int>& nums)
{
int count = 1, marked = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i + 1] == nums[marked]) {
count++;
if (count == 5) return nums[marked];
}
else
{
marked = i + 1;
count = 1;
}
}
return 0;
}
Supposing the vector contain a value repeated 5 times, the 2 first comparisons are executed 5 to 10 times, the third is execute 5 times. Which total to between 15 to 25 comparisons for this code.
Your code is checking if a value is repeated 5 times before answering the value what is that value. You are not asked to check if there is a value repeated 5 times or not, this is a knowledge.
You are just asked to find which one. And you are allowed 2 comparisons.
[Update]
Quote:
question from geeksforgeeks.com
The question look like a little challenge, but with a careful analyze, you can find that 1 comparison is enough to know the answer.
[Update for Chill60]
Chill60 wrote:
Put me out my misery please.
Sure. You just have to do a visual analyze.
if vector is
9 elements, they look like:
1 1 1 1
1 2 3 4 5
1 2 3 4
5 5 5 5 5
return nums[4];
is the answer, no test required, because element 4 is always in repeated value.
if vector is
10 elements, they look like:
1 1 1
1 1 2 3 4 5 6
1 2 3
4 4 4 4 4 5 6
1 2 3
4 5 5 5 5
5 6
1 2 3
4 5 6 6 6
6 6
if (nums[3]==nums[4])
return nums[4]; else
return nums[8];
if test fails, element 8 is the answer.
The same answer fits to vector size up to 13:
1 2 3
4 5 5 5 5
5 6 7 8 9
1 2 3
4 5 6 7 8
9 9 9 9 9