@Dhritiman, It's good algo man!!!The only thing is we are destroying
the array but also that's mandatory as only o(n) complexity we are
interested in.
As Somebody wanted the code, here I am attaching below: -
int a[SIZE_A] = {0,2,1,4,0};
int i = 0, dup = 0, pos = 0, t =0;
while (i< 5)
{
if (a[i] == i)
i++;
else if (a[a[i]] == a[i])
{
dup = a[i];
printf ("\nduplicated element is [%d]", dup);
pos = i;
i++;
}
else
{
t= a[i];
a[i] = a[a[i]];
a[t] = t;
}
}
printf ("\nmissing element is [%d]", pos);
Cheers,
Ankit Sinha!!!!
On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das <[email protected]> wrote:
> @Dinesh,
> Yes, we can't apply this method, if that's not allowed.
>
> On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal <[email protected]> wrote:
>>
>>
>> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das <[email protected]>
>> wrote:
>>>
>>> Given a array, A[1..n], do the following.
>>> Start from i=1 and try placing each number in its correct position in the
>>> array.
>>> If the number is already in its correct position, go ahead. if (A[i] ==
>>> i) , i++
>>> else if the number was already restored to its correct position, then it
>>> is
>>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup =
>>> A[i], i++ ;
>>> else
>>> swap the elements at the current index i and that at A[i]'s correct
>>> position in the array.
>>> continue this until all numbers are placed in their correct position in
>>> the array
>>> Finally, A[missing] will be dup.
>>> O(n)
>>
>>
>> @Dharitiman, good solution man. No expensive computation, no extra memory
>> required. Only problem is it will change the input array to sorted order
>> which may not be desired.
>>
>>>
>>> On Wed, Sep 1, 2010 at 7:14 AM, Dave <[email protected]> wrote:
>>>>
>>>> Suppose that x is duplicated and y is omitted. Then the sum of the
>>>> numbers would be 5050 + x - y. Similarly, the sums of the squares of
>>>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of
>>>> squares of the numbers and solve the resulting equations for x and y.
>>>>
>>>> Dave
>>>>
>>>> On Aug 31, 1:57 pm, Raj Jagvanshi <[email protected]> wrote:
>>>> > There is an array having distinct 100 elements from 1 to 100
>>>> > but by mistake some no is duplicated and a no is missed.
>>>> > Find the duplicate no and missing no.
>>>> >
>>>> > Thanks
>>>> > Raj Jagvanshi
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
>> --
>> Dinesh Bansal
>> The Law of Win says, "Let's not do it your way or my way; let's do it the
>> best way."
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
