Click here to Skip to main content
13,199,852 members (65,780 online)
Rate this:
 
Please Sign up or sign in to vote.
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
ppolymorphe107.8K
v3
Rate this: bad
 
good
Please Sign up or sign in to vote.

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
  Permalink  
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
ppolymorphe 22-May-17 8:16am
   
Thank you
Rate this: bad
 
good
Please Sign up or sign in to vote.

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
    answer = index[0]
ELSE IF (index[8]==index[9]) THEN  // two comparision
    answer = index[8]
  Permalink  
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.
ppolymorphe 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.
ppolymorphe 21-May-17 11:25am
   
update my answer for you.
Rate this: bad
 
good
Please Sign up or sign in to vote.

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 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...
  Permalink  
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)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy |
Web04 | 2.8.171020.1 | Last Updated 22 May 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100