After working on it quite a bit I got an O(log n) algorithm working.
For small cases (size < 10) it sequentially finds the solution.
For larger cases it uses a binary search:
Starting at the midpoint, find the left and the right ends of the
region with values equal to the value at the midpoint. T
it is O(n) and complex unnecessary
On Aug 24, 3:58 pm, Ankit Minglani wrote:
> How about this :
> We use a divide and conquer approach and since the array is sorted.
> We find the middle element and check its value with its immediate left and
> right element .. it must match with anyone of them .
my binary search method in Ruby is similar to Don's. I tested with
array [1,1,2,2,2,2,3,3,9,14,14] , to which the answer should be 9,
and now added what I call "fluff" (meaningless numbers) to either:
the left (300_000 zeroes at the head) , making it difficult for direct
approach; the middle (
{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
comes under this problem?
surender
On Thu, Aug 25, 2011 at 8:12 AM, Dave wrote:
> @Shailesh: Sir, your response is unresponsive, because the original
> poster specifically asked for a solution that was < O(n). Please don't
@Shailesh: Sir, your response is unresponsive, because the original
poster specifically asked for a solution that was < O(n). Please don't
waste our time giving answers that so obviously do not meet the
problem statement.
Dave
On Aug 24, 6:33 pm, smb wrote:
> XOR all the elements, the answer is
XOR all the elements, the answer is the number you want.
On Aug 24, 5:11 pm, Don wrote:
> I assume that "elements in pairs" means that each value occurs exactly
> twice except for the one single.
> This algorithm is O(log n) and is nonrecursive. Writing it recursively
> would make it a couple of
I assume that "elements in pairs" means that each value occurs exactly
twice except for the one single.
This algorithm is O(log n) and is nonrecursive. Writing it recursively
would make it a couple of lines shorter, but because it is purely tail
recursion, that is not necessary.
// Given an array
mine approach is log(n)
check it out first
On Thu, Aug 25, 2011 at 1:21 AM, Don wrote:
> I'm going to assume that "elements in pairs" means exactly two of each
> element except for the one which is missing it's pair.
> The recursive solution is simple, but it only uses tail recursion, so
> it i
I'm going to assume that "elements in pairs" means exactly two of each
element except for the one which is missing it's pair.
The recursive solution is simple, but it only uses tail recursion, so
it is worthwhile to do it iteratively.
int findSingle(int *a, int size)
{
int result;
while(1)
See interviewer said that it can be done in wrote:
> Hi
>
> The ques explicitly said the elements are in pairs ...But the one given by
> sanjay has more than 2 2's ...that question cant be done using bsearch then
>
> On Wed, Aug 24, 2011 at 6:21 PM, Sanjay Rajpal wrote:
>
>> yes this is the only
flag=0;
for(int i=0;ihttp://groups.google.com/group/algogeeks?hl=en.
Hi
The ques explicitly said the elements are in pairs ...But the one given by
sanjay has more than 2 2's ...that question cant be done using bsearch then
On Wed, Aug 24, 2011 at 6:21 PM, Sanjay Rajpal wrote:
> yes this is the only one till now, but i think we can do better also.
>
> Hope a bett
yes this is the only one till now, but i think we can do better also.
Hope a better solution will be posted by someone soon.
Sanju
:)
On Wed, Aug 24, 2011 at 5:22 AM, Venkat wrote:
> @Sanju: For your input both above solution wont work...
>
> Do you ve any soultion for your input??
> For your
@Sanju: For your input both above solution wont work...
Do you ve any soultion for your input??
For your input Xor all numbers - will give you the result:)
but its O(n)
Anyway your input allow everyone to think little wider than Binay
search.
Thanks
Venkat
On Aug 24, 4:05 pm, Sanjay R
@Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur
solution work ?
Sanju
:)
On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani wrote:
> How about this :
> We use a divide and conquer approach and since the array is sorted.
> We find the middle element and check its value with
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide the
array again
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array
17 matches
Mail list logo
