[algogeeks] Re: Try this ..
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 something like that instead of a bit) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try 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 elements in array.So, a/b=M1/M and |a-b|=|S-S1|.Using these two equations we getb = M*|S-S1|/|M-M1|.a = M1*b/M = M1|S-S1|/|M-M1|.
This surely can be done in O(n) and code for the same goes likeS1=0; M1=1; M=1; S=N*(N+1)/2.for(i=0;iN;i++){S1+=arr[i];M1*=arr[i];M*=(i+1);}t1=abs(S-S1); t2=abs(M1-M);Repeated_element = M1*t1/t2;
Missing_element = M*t1/t2;Thanks,Kamlesh
--~--~-~--~~~---~--~~
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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 recursion tree, at each level of the tree
//each number will show up at most one time. Since there are
//always a constant number of levels in the tree
//(sizeof(unsigned int) * 8 - 1) this function runs in O(n)
unsigned int findDup(listunsigned int l, unsigned mask)
{
if(l.size() 2)
return 0;
else if(l.size() == 2 mask == 0)
return l.front();
listunsigned int lo, lz;
for(listunsigned int::iterator it = l.begin(); it != l.end(); it++)
if(*it mask)
lo.push_back(*it);
else
lz.push_back(*it);
mask = mask 1;
return findDup(lo, mask) + findDup(lz, mask);
}
int main()
{
unsigned int nums[] = {3, 77, 28, 89, 2777, 431, 24, 1, 99, 8,
78, 88, 2, 3};
listunsigned int l(nums, nums + sizeof(nums) / sizeof(unsigned
int));
cout findDup(l, 1 (sizeof(unsigned int) * 8 - 1)) endl;
cin.get();
return 0;
}
shashi_genius wrote:
There are n numbers with all (n-1) unique numbers, except for one which
is repeating.
Find out the repeating number in O(n) complexity.
--~--~-~--~~~---~--~~
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 group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 = M1|S-S1|/|M-M1|.
This surely can be done in O(n) and code for the same goes like
S1=0; M1=1; M=1; S=N*(N+1)/2.
for(i=0;iN;i++)
{
S1+=arr[i];
M1*=arr[i];
M*=(i+1);
}
t1=abs(S-S1); t2=abs(M1-M);
Repeated_element = M1*t1/t2;
Missing_element = M*t1/t2;
Thanks,
Kamlesh
--~--~-~--~~~---~--~~
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 group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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, --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
@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 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 eq1 obtain the sum of the squares of all the numbers, say sqSum so, sqSum - sqr(y) + sqr(x) = n(n+1)(2n+1) / 6eq2 Solving the above two equations will give the actual replaced number ; --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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. --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 8/15/06, ridvansg [EMAIL PROTECTED] wrote: 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 therepeating number.The complexity: O(k*n) = O(n)-- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 unique numbers and 1 no. repeats only , each elt will keep on being insertwed at end of the list while at the repeated element u could print the element and exit On 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote: 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 would endure so many collisions, ... the complexity can then be worst-case O(n^2) ... On 8/15/06, ridvansg [EMAIL PROTECTED] wrote: 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) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 sure About the soln. but here goes Create a link list The node contains the number along with the list pointer. whilecreating the list impose a condition on insertion to chk forrepetion.. i.e while traversing the list chk if the element is already inserted or not .given that n-1 are unique numbers and 1 no. repeatsonly , each elt will keep on being insertwed at end of the list whileat the repeated element u could print the element and exitOn 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote: 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 would endure so many collisions, ... the complexity can then be worst-case O(n^2) ... On 8/15/06, ridvansg [EMAIL PROTECTED] wrote: 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) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 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). ~Vishal On 8/15/06, akshay ranjan [EMAIL PROTECTED] wrote: 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 unique numbers and 1 no. repeats only , each elt will keep on being insertwed at end of the list while at the repeated element u could print the element and exit On 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote: 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 would endure so many collisions, ... the complexity can then be worst-case O(n^2) ... On 8/15/06, ridvansg [EMAIL PROTECTED] wrote: 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) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 end of the list ( not sorting ). while traversing to end of the list jst chk if the element is already present in thelistOn 8/16/06, Vishal [EMAIL PROTECTED] wrote: 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). ~Vishal On 8/15/06, akshay ranjan [EMAIL PROTECTED] wrote: 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 unique numbers and 1 no. repeats only , each elt will keep on being insertwed at end of the list while at the repeated element u could print the element and exit On 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote: 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 would endure so many collisions, ... the complexity can then be worst-case O(n^2) ... On 8/15/06, ridvansg [EMAIL PROTECTED] wrote: Hi, here is the solution.1. Create a hashtable .2. Go through the numbers inserting each into the hashtable. Wheninsert the number check if it already exists, if so - this is the repeating number. The complexity: O(k*n) = O(n) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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, akshay ranjan [EMAIL PROTECTED] wrote: 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 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). ~Vishal On 8/15/06, akshay ranjan [EMAIL PROTECTED] wrote: 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 unique numbers and 1 no. repeats only , each elt will keep on being insertwed at end of the list while at the repeated element u could print the element and exit On 8/16/06, Lego Haryanto [EMAIL PROTECTED] wrote: 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 would endure so many collisions, ... the complexity can then be worst-case O(n^2) ... On 8/15/06, ridvansg [EMAIL PROTECTED] wrote: 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) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~-~--~~~---~--~~ 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 group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Try this ..
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 To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
