girsh and kamlesh: that may work if the (n-1) numbers are integers 1 to
n. What if they can be anything. (from your S(n) = n*(n+1) / 2 ) )
adak : distribution sort - this is effectively the same as the bitmap
thing which Lego Haryanto mentioned in the beginning. (we're only using
a byte or
I didnt understand what you mean. Please clarify.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this
i don't think the repeat numberis limited toonly one.
Anyway, it's a program problem, not a math one.
2006/8/24, Kamlesh [EMAIL PROTECTED]:
Hi all,Supposea -repeated element.b -missing element.S -Sum of 1-N elements=N*(N+1)/2.
M -Product of 1-N elements=N!.S1-Sum of elements in arrayM1-Product of
Here is a program that might be bad but is theoretically O(n) for
unsigned integers. You can just cast signed integers to unsiged ones
and then cast the result back to a signed integer to get it to work
with signed integers.
#include iostream
#include list
using namespace std;
//consider the
Hi all,
Suppose
a -repeated element.
b -missing element.
S -Sum of 1-N elements=N*(N+1)/2.
M -Product of 1-N elements=N!.
S1-Sum of elements in array
M1-Product of elements in array.
So, a/b=M1/M and |a-b|=|S-S1|.
Using these two equations we get
b = M*|S-S1|/|M-M1|.
a = M1*b/M =
Hi
I have one solution probably this might work.
Since the numbers are all unique you can find the sum of all the
numbers
in the array.
Also find the sum of n numbers n*(n+1)/2.
Subtract the second one from the first one you will get the number.
Thanks and Regards,
Girish Dinne,
@girish,
I think U didnt understand the problem correctly... it is not the
problem of finding the missing number. A missing number is replaced by
some other number which is already existing in the list.
--~--~-~--~~~---~--~~
You received this message
I will try to give one solution for this vaguely... Correct me if Im
wrong. But, the solution suffers overflow problem if implemented.
Assume that the number which got replaced is x and the number which
replaced it is y
obtain the sum of all the numbers, say Sum
so, Sum - y + x = n(n+1) / 2
for example
1 2 3 4 5 6 7 8 9 9
So there are 10 number with all the 9 unique numbers.
So find the sum of 9 numbers 9*(9+1)/2 = 45
Find the sum of the given array 54
Subtract 54 -45 you will get the answer.
but this work if all the number from 1 to n-1 are there in the array.
Try this:
Do your own homework.
Or post a partial solution or even a thought process.
Would it help if I put ! at the end ??
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Hi, here is the solution.
1. Create a hashtable .
2. Go through the numbers inserting each into the hashtable. When
insert the number check if it already exists, if so - this is the
repeating number.
The complexity: O(k*n) = O(n)
--~--~-~--~~~---~--~~
You
Not sure about the line O(k * n) = O(n) ...
That's probably assuming the hash-table doesn't have collision, which pretty much is O(1). What if somehow the numbers are chosen so that a particular hashtable wouldendure so many collisions, ... the complexity can then be worst-case O(n^2) ...
On
Not sure About the soln. but here goes
Create a link list
The node contains the number along with the list pointer. while
creating the list impose a condition on insertion to chk for
repetion.. i.e while traversing the list chk if the element is already
inserted or not .given that n-1 are
The simple way would be (for random numbers scenario) to sort the array - O(n log n) - and then traverse through the array to find the repeated element - O(n).The creation of link list is nothing but insertion sort, which is O(n^2).
~VishalOn 8/15/06, akshay ranjan [EMAIL PROTECTED] wrote:
Not
the link is not being sorted the elemnts are being read frm the array
and inserted at the end of the list ( not sorting ). while traversing
to end of the list jst chk if the element is already present in the
list
On 8/16/06, Vishal [EMAIL PROTECTED] wrote:
The simple way would be (for random
That's still an O(n^2) ... I believe your word traversing is O(n) by itself ... And you're going to be traversing to the end of the list for each insertion.
On 8/15/06, akshay ranjan [EMAIL PROTECTED] wrote:
the link is not being sorted the elemnts are being read frm the arrayand inserted at the
ur right it does come o(n^2) as search is carried out n times
On 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote:
That's still an O(n^2) ... I believe your word traversing is O(n) by
itself ... And you're going to be traversing to the end of the list for each
insertion.
On 8/15/06,
the numbers are not sorted and nothing is known about the range of the
numbers.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
18 matches
Mail list logo
