Click here to Skip to main content
15,893,904 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
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
C++
// 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 20:41pm
v3

Quote:
I am not sure what "two comparisons" means here.

C++
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
C++
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
C++
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
 
Share this answer
 
v5
Comments
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
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
    answer = index[0]
ELSE IF (index[8]==index[9]) THEN  // two comparision
    answer = index[8]
 
Share this answer
 
Comments
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.
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 ifs, two whiles, or maybe one for with an if inside it. Basically, two expressions which return a boolean result. But I could be wrong...
 
Share this answer
 
Comments
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)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900