13,704,995 members
See more:
This is the exact question from the website.

Given a sorted array having 10 elements which contains 6 different numbers in which only 1 number is repeated five times. Your task is to find the duplicate number using two comparisons only.

I am not sure what "two comparisons" means here. Could you please shed some light on it. Thank you.

What I have tried:

This is my code
```// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iso646.h>
#include <vector>
#include <string>
#include<iostream>

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;
}```
Posted 20-May-17 16:35pm
Updated 20-May-17 20:41pm
v3

## Solution 1

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++) // Here is a comparison
{
if (nums[i + 1] == nums[marked]) // Here is a comparison
{
count++;

if (count == 5) // Here is a comparison
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]; // nums{3] is also the answer
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
v5
21-May-17 2:43am

OK, so comparison just means when I am using the boolean operator to compare two quantities. In my code, since I have used a loop, I am comparing the same quantities multiple times and hence I have violated the requirement of the question. That makes sense. Thank you very much for your help.
CHill60 22-May-17 7:49am

Thank you! Quite elegant. I was too focussed on comparing nums[4] and nums[5] to see what was right in front of me. 5'd
Patrice T 22-May-17 8:16am

Thank you

## Solution 3

Since the array is sorted, the 5 duplicate numbers must be grouped together in the array.
Since there are only 10 elements in the array, there are 3 scenarios where these 5 duplicate numbers can be located:
1. On the first half of the array;
2. On the second half of the array; or
3. Spanning across the midpoint of the array!
Having analyzed and understand the problem, the algorithm is clear:
```SET answer = index[4] // midpoint by default, assuming scenario 3
IF (index[0]==index[1]) THEN // one comparision
ELSE IF (index[8]==index[9]) THEN  // two comparision
21-May-17 2:44am

Thank you very much. I now understand what is meant by two comparisons. My code uses multiple comparisons due to for loop and hence it is wrong.
Patrice T 21-May-17 3:11am

Hi Peter.
Have you seen that 1 comparison is enough ?
CHill60 21-May-17 6:30am

Ok @ppolymorphe - you've got me intriqued.
I can see how a single comparison is required for any pattern except where the repeated number is the first 5 or last 5 entries. I just can't see how to distinguish between those 2 scenarios without a further comparison :(
Put me out my misery please.
Patrice T 21-May-17 11:25am

## Solution 2

I'd suggest that the place to ask if the site you got the question from, rather than a different website that has no connection with it.

At a guess - and that's all it can be since we know no more about the question than you do - your code can have two tests only: two `if`s, two `while`s, or maybe one `for` with an `if` inside it. Basically, two expressions which return a boolean result. But I could be wrong...
21-May-17 2:42am

Thank you for your help. I really appreciate it.

Top Experts
Last 24hrsThis month
 OriginalGriff 276 Dave Kreskowiak 145 Richard Deeming 135 Maciej Los 120 Richard MacCutchan 75
 OriginalGriff 6,523 Maciej Los 1,990 Patrice T 1,735 Richard MacCutchan 1,553 Richard Deeming 956