Prev: The RUN CHASE: A Challenge for the Programmer in U...
Next: "Variable Depth" Problem
From: mohangupta13 on 5 Apr 2010 15:14
hello all,
Hope everyone is in the pink of perfection ! ...i was out for a long
time i think ..

anyway i had two problems to discuss ...

1. Given an array in which only one pair of number ( say integers ) is
repeating ,all other numbers are distinct ..what is the best possible
algo to find such number ..?? ( say for both cases when we dont have
any constraint on the numbers and when we do define some constrain say
the range of possible numbers in the array)...

2. (this may not be suited here but still ) What is the probability
that out of 5 persons, no two person have birthday on the same day of
a week (..i.e all 5 have birthdays on different days of a week)..???

well this one i tried like :
probability that on a particular day
we have atleast 2 birthdays= ( (5X4)/7^2 + (5X4X3)/7^3 +(5X4X3X2)/7^4
+ (5x4x3x2x1)/7^5)===0.63...(approx)

but how to proceed from here ... this is valid for a particular day...
how do account or extend this to apply to all 7 days of the week so
that no day can have more than 1 birthday .

hope i am being meaningful !

regards
Mohan Gupta
From: Willem on 5 Apr 2010 15:53
mohangupta13 wrote:
) hello all,
) Hope everyone is in the pink of perfection ! ...i was out for a long
) time i think ..
)
) anyway i had two problems to discuss ...
)
) 1. Given an array in which only one pair of number ( say integers ) is
) repeating ,all other numbers are distinct ..what is the best possible
) algo to find such number ..?? ( say for both cases when we dont have
) any constraint on the numbers and when we do define some constrain say
) the range of possible numbers in the array)...

One pair is repeating ? I'm not sure I understand exactly what you mean.
An example would be helpful. The algorithm depends a lot on what exactly
you can or cannot say about the data.

The most generic way to find doubles is to sort the array, then the doubles
will be next to each other. But this sounds a lot like a puzzle that has
a much more trick-y answer.

) 2. (this may not be suited here but still ) What is the probability
) that out of 5 persons, no two person have birthday on the same day of
) a week (..i.e all 5 have birthdays on different days of a week)..???
)
) well this one i tried like :
) probability that on a particular day
) we have atleast 2 birthdays= ( (5X4)/7^2 + (5X4X3)/7^3 +(5X4X3X2)/7^4
) + (5x4x3x2x1)/7^5)===0.63...(approx)
)
) but how to proceed from here ... this is valid for a particular day...
) how do account or extend this to apply to all 7 days of the week so
) that no day can have more than 1 birthday .

That's the wrong way to go about it.

What you want to do is calculate the probability that all people
have their birthday on a different day of the week.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: Kai-Uwe Bux on 5 Apr 2010 15:57
mohangupta13 wrote:

> hello all,
> Hope everyone is in the pink of perfection ! ...i was out for a long
> time i think ..
>
> anyway i had two problems to discuss ...
>
> 1. Given an array in which only one pair of number ( say integers ) is
> repeating ,all other numbers are distinct ..what is the best possible
> algo to find such number ..?? ( say for both cases when we dont have
> any constraint on the numbers and when we do define some constrain say
> the range of possible numbers in the array)...

I would start with:

a) sort the array
b) find the two equal (and now adjacent!) slots

Now, if there is some constraint, it would be cool to know the constraint.
E.g., if the array has length n and the integers are from [0,n), then one is
repeating and one is missing, and you can find out which by adding all
numbers in the array (mod n).


> 2. (this may not be suited here but still ) What is the probability
> that out of 5 persons, no two person have birthday on the same day of
> a week (..i.e all 5 have birthdays on different days of a week)..???

7/7 * 6/7 * 5/7 * 4/7 *3/7 \approx 0.15

(the first is free, the second has to avoid one day of the week, two days
are blocked for the 3rd, ...)

Also: google "birthday paradox".


Best

Kai-Uwe Bux
From: Richard Heathfield on 5 Apr 2010 16:57
mohangupta13 wrote:
> hello all,
> Hope everyone is in the pink of perfection ! ...i was out for a long
> time i think ..
>
> anyway i had two problems to discuss ...
>
> 1. Given an array in which only one pair of number ( say integers ) is
> repeating ,all other numbers are distinct ..what is the best possible
> algo to find such number ..?? ( say for both cases when we dont have
> any constraint on the numbers and when we do define some constrain say
> the range of possible numbers in the array)...

Lacking a definition of "best", the simplest way is to sort the array,
and then iterate through it looking for adjacent elements with the same
value.

> 2. (this may not be suited here but still ) What is the probability
> that out of 5 persons, no two person have birthday on the same day of
> a week (..i.e all 5 have birthdays on different days of a week)..???

7! / (7-5)!
-----------
5
7

= 7 * 6 * 5 * 4 * 3
-----------------
7 * 7 * 7 * 7 * 7

= 360/2401, or slightly over 0.14993752603.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
From: mohangupta13 on 6 Apr 2010 08:47
first of all. thanks a lot for your answers ...



On Apr 6, 1:57 am, Richard Heathfield <r...(a)see.sig.invalid> wrote:
> mohangupta13 wrote:
> > hello all,
> > Hope everyone is in the pink of perfection ! ...i was out for a long
> > time i think ..
>
> > anyway i had two problems to discuss ...
>
> > 1. Given an array in which only one pair of number ( say integers ) is
> > repeating ,all other numbers are distinct ..what is the best possible
> > algo to find such number ..?? ( say for both cases when we dont have
> > any constraint on the numbers and when we do define some constrain say
> > the range of possible numbers in the array)...
>
> Lacking a definition of "best", the simplest way is to sort the array,
> and then iterate through it looking for adjacent elements with the same
> value.
>

for the first problem what if we have a constraint that the range of
numbers is between [0----kn] for some constant k...now what is the
best possible way to do this ??
( and is it possible in O(n) time with using a constant storage ..and
if not how can we prove that fact ???)


> > 2. (this may not be suited here but still ) What is the probability
> > that out of 5 persons, no two person have birthday on the same day of
> > a week (..i.e all 5 have birthdays on different days of a week)..???
>
> 7! / (7-5)!
> -----------
>        5
>       7
>
> = 7 * 6 * 5 * 4 * 3
>    -----------------
>    7 * 7 * 7 * 7 * 7
>
> = 360/2401, or slightly over 0.14993752603.
>
> --
> Richard Heathfield <http://www.cpax.org.uk>
> Email: -http://www. +rjh@
> "Usenet is a strange place" - dmr 29 July 1999
> Sig line vacant - apply within

regards,
Mohan

 |  Next  |  Last
Pages: 1 2
Prev: The RUN CHASE: A Challenge for the Programmer in U...
Next: "Variable Depth" Problem