DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 223--------------------------------------------------
find the 2 numbers
By: dinesh Date: November 27, 2012, 8:38 am
---------------------------------------------------------
Given an array of n elements with on exacly 2 elements repeated
twice. Can you give an algorithm to find both of them in O(n)
time?
#Post#: 224--------------------------------------------------
Re: find the 2 numbers
By: kranthipls Date: November 27, 2012, 8:47 am
---------------------------------------------------------
What is the range of the numbers? Is it that they can be
anything across the integer range...
#Post#: 227--------------------------------------------------
Re: find the 2 numbers
By: ravusairam Date: November 27, 2012, 9:04 am
---------------------------------------------------------
I think the range n should be given.
if so then we can take the sum of the given elements - sum of
(1....n) = (a+b) - > where a and b are repeated
we take product of given elements / product of (1......n) = a*b
so with these two equations we can solve a and b.
Am I correct?
#Post#: 230--------------------------------------------------
Re: find the 2 numbers
By: kpr29 Date: November 27, 2012, 9:10 am
---------------------------------------------------------
@Ravu: Nice.......... Has resemblence with basket of apples
problem
#Post#: 233--------------------------------------------------
Re: find the 2 numbers
By: ravusairam Date: November 27, 2012, 9:31 am
---------------------------------------------------------
@yes it is an extension for that apple problem
#Post#: 236--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: November 27, 2012, 9:39 am
---------------------------------------------------------
That answer is correct if the range of numbers is from 1 to n.
If the range is not given, can you still find a solution...
#Post#: 238--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: November 27, 2012, 9:42 am
---------------------------------------------------------
Hint:
The solution for the above problem is also a solution for this
problem.
Given an array in which all numbers except two are repeated
twice. (i.e. we have 2n+2 numbers and n numbers are occurring
twice and remaining two have occurred once). Find those two
numbers in the most efficient way.
#Post#: 313--------------------------------------------------
Re: find the 2 numbers
By: srini Date: December 4, 2012, 3:25 am
---------------------------------------------------------
does sorting give us answer???
Idea is to sort the array, then if you find the difference
between the pairs (a_[i],a[i+1]),(a[i+2],a[i+3)),...you will get
zero for all pairs except for the non repeated numbers.
#Post#: 322--------------------------------------------------
Re: find the 2 numbers
By: dinesh Date: December 4, 2012, 8:26 am
---------------------------------------------------------
But can the solution be obtained in O(n) time?
#Post#: 325--------------------------------------------------
Re: find the 2 numbers
By: kranthipls Date: December 4, 2012, 8:45 am
---------------------------------------------------------
Let me give you solution for the first one.........
Find the largest element in the given numbers and declare an
array of integers with the size of the maximum element and
initialize it to zero.
Now traverse through the numbers and starting incrementing the
array......... with that particular index.........
Once the incrementing is done the element with 2 as value is
the repeated one
*****************************************************
DIR Next Page