13,804,222 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
Updated 20-May-17 21: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
Member 13192781 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
Member 13192781 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

update my answer for you.

## 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...
Member 13192781 21-May-17 2:42am

Thank you for your help. I really appreciate it.

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

Top Experts
Last 24hrsThis month
 OriginalGriff 300 CPallini 105 Dave Kreskowiak 80 Wendelius 80 MadMyche 55
 OriginalGriff 3,243 Richard MacCutchan 2,321 CPallini 1,148 RickZeeland 900 Dave Kreskowiak 850