Re: [algogeeks] How to remove duplicate element from array in one pass.
int x;
set int s;
set int :: iterator it;
for(i=1;i=n;i++){
cin x;
s.insert(x);
}
for(it=s.begin(); it!=s.end();it++)
cout *it endl;
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Thu, Jun 2, 2011 at 11:36 PM, sanjay ahuja sanjayahuja.i...@gmail.comwrote:
similar implementation is available in STL also, you can use STL maps.
On Fri, Jun 3, 2011 at 7:50 AM, D.N.Vishwakarma@IITR deok...@gmail.com
wrote:
question is in c++
On Fri, Jun 3, 2011 at 7:48 AM, sanjay ahuja sanjayahuja.i...@gmail.com
wrote:
you can use Java HashTable/HashMap to store key value pair, where Key
being the element stored in array and Value being the index of the
element. Any duplicate insert on key will replace the value of that
Key. After finishing all elements retrieve all Key, value pair stored
in HashMap.
Let me know If I am missing something!!
But if you want to make your own hashtable. Then we can find the range
of elements in one pass and then carefully choose some hash function
to avoid collision and make hash on key. But this will not be one
pass.
On Fri, Jun 3, 2011 at 7:31 AM, D.N.Vishwakarma@IITR deok...@gmail.com
wrote:
@Sanjay ahuja
yes ans is required in O(n)
how it can be done by hashing?
On Fri, Jun 3, 2011 at 1:19 AM, Supraja Jayakumar
suprajasank...@gmail.com
wrote:
Hi
I think multi hash table will solve this problem.
Thanks
Supraja J
On Thu, Jun 2, 2011 at 1:37 PM, Harshal hc4...@gmail.com wrote:
But I think the solution required is O(n) (one pass). So, O(nlogn)
is
not
what the author wants anyway. Hashing is an option but we dont know
the
range of the elements in the array. So, in case when all keys hash
into the
same place, the worst case is still O(n^2).
suppose our hash function is h(n) = n mod 10.
array: 2,12,32,52,42.
On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote:
you can check if the element to be inserted next is same as the
node
value while inserting itself. Why to do a separate inorder
traversal..
On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar
suprajasank...@gmail.com wrote:
Hi
Inserting into BST and break on same element will detect
duplicates.
But in any case, this is still O(2n) ? - once for inserting them
in
to
the tree
and another for the inorder read.
Correct me if wrong.
Rgds
Supraja J
On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote:
@Anurag: XOR wont work here, 1 element is repeated, not 1 element
is
unique. Read the question again.
Keep inserting elements in a BST and break once you find the same
element. O(nlogn)
On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain
anuragnar...@gmail.com wrote:
take X-OR of all the elements.the one which has no duplicate
will
be left and rest all will be reduced to zero.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Harshal Choudhary,
III Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
U
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Harshal Choudhary,
III Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
Harshal Choudhary,
III Year B.Tech CSE,
NIT Surathkal, Karnataka, India.
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
U
--
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,
Re: [algogeeks] How to remove duplicate element from array in one pass.
Python implementation using dictionary/hash table
# main function
def main():
# 'dicti' is a hash table
# 's' is string
dicti = {};
s = asldhj aldalkd7^Awu3e8 ue8u1o2h3o82708q2
# iterting over the string
for i in range(len(s)):
# if the character is not in hash table ,then store the character with value
==1
# and print(or store) the echaracter
if not s[i] in dicti:
dicti[s[i]] = 1
print s[i]
if __name__ == __main__:
main()
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
C implementation:
#include stdio.h
int main()
{
char arr[100]=ash ;alsdfasf jahfjkjfhsakfjha;
int i;
int table[256] = {0};
int a;
for(i = 0; i=10; i++)
{
// 'a ' store the ASCII value of arr[i]
a = arr[i];
if (table[a] == 0)
{
table[a] = 1;
printf(%c, arr[i]);
}
}
printf(/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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
How can we be sure that array elements are characters?
They can be big number, strings or anything.
On Fri, Jun 3, 2011 at 5:23 PM, Naveen Agrawal nav.coo...@gmail.com wrote:
C implementation:
#include stdio.h
int main()
{
char arr[100]=ash ;alsdfasf jahfjkjfhsakfjha;
int i;
int table[256] = {0};
int a;
for(i = 0; i=10; i++)
{
// 'a ' store the ASCII value of arr[i]
a = arr[i];
if (table[a] == 0)
{
table[a] = 1;
printf(%c, arr[i]);
}
}
printf(/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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Cheers
Naveen Kumar
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
@Naveen Kumar 1. For Python Implementation I have used string just for example. You can have a list(or array) . Then iterate it through each element of list instead of above implementation(iterating through each character of string) . Rest of the thing will remain same. 2. For C implementation If it is not string, then you have to use hash table(available in STL) as pointed out by sanjay ahuja -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] How to remove duplicate element from array in one pass.
better than O(n2) algo -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
Hi
Mere removal is enough ? Shifting not necessary ?
If yes, then
we can have something like this. But let me know if this sounds ok and any
further improvements.
int chars = new int[256];
int values = new int[10]; // say 10 chars
for(i = 0; i 10; i++) {
int charVal = toascii(values[i]);
chars[charValue]++;
if(chars[charValue] 1)
// remove from array.
values[i] = 0; // some other sentinel value ?
}
Rgds
Supraja J
On Thu, Jun 2, 2011 at 12:19 PM, D.N.Vishwakarma@IITR deok...@gmail.comwrote:
better than O(n2) algo
--
**With Regards
Deoki Nandan Vishwakarma
IITR MCA
Mathematics Department*
*
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
U
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
sorry the above algo will not work in case we have more than one single element -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
@Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.comwrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
If use of hash table is allowed. then it can be done in o(n) On Fri, Jun 3, 2011 at 12:41 AM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.com wrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd Powai, Mumbai (400076) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.comwrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.comwrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42. On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote: you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.comwrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
Hi I think multi hash table will solve this problem. Thanks Supraja J On Thu, Jun 2, 2011 at 1:37 PM, Harshal hc4...@gmail.com wrote: But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42. On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote: you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.comwrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
@Sanjay ahuja yes ans is required in O(n) how it can be done by hashing? On Fri, Jun 3, 2011 at 1:19 AM, Supraja Jayakumar suprajasank...@gmail.comwrote: Hi I think multi hash table will solve this problem. Thanks Supraja J On Thu, Jun 2, 2011 at 1:37 PM, Harshal hc4...@gmail.com wrote: But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42. On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote: you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.com wrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to remove duplicate element from array in one pass.
you can use Java HashTable/HashMap to store key value pair, where Key being the element stored in array and Value being the index of the element. Any duplicate insert on key will replace the value of that Key. After finishing all elements retrieve all Key, value pair stored in HashMap. Let me know If I am missing something!! But if you want to make your own hashtable. Then we can find the range of elements in one pass and then carefully choose some hash function to avoid collision and make hash on key. But this will not be one pass. On Fri, Jun 3, 2011 at 7:31 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: @Sanjay ahuja yes ans is required in O(n) how it can be done by hashing? On Fri, Jun 3, 2011 at 1:19 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi I think multi hash table will solve this problem. Thanks Supraja J On Thu, Jun 2, 2011 at 1:37 PM, Harshal hc4...@gmail.com wrote: But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42. On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote: you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.com wrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sanjay Ahuja, Analyst, Financing Prime Brokerage Nomura Securities India Pvt. Ltd -- 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
Re: [algogeeks] How to remove duplicate element from array in one pass.
question is in c++ On Fri, Jun 3, 2011 at 7:48 AM, sanjay ahuja sanjayahuja.i...@gmail.comwrote: you can use Java HashTable/HashMap to store key value pair, where Key being the element stored in array and Value being the index of the element. Any duplicate insert on key will replace the value of that Key. After finishing all elements retrieve all Key, value pair stored in HashMap. Let me know If I am missing something!! But if you want to make your own hashtable. Then we can find the range of elements in one pass and then carefully choose some hash function to avoid collision and make hash on key. But this will not be one pass. On Fri, Jun 3, 2011 at 7:31 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: @Sanjay ahuja yes ans is required in O(n) how it can be done by hashing? On Fri, Jun 3, 2011 at 1:19 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi I think multi hash table will solve this problem. Thanks Supraja J On Thu, Jun 2, 2011 at 1:37 PM, Harshal hc4...@gmail.com wrote: But I think the solution required is O(n) (one pass). So, O(nlogn) is not what the author wants anyway. Hashing is an option but we dont know the range of the elements in the array. So, in case when all keys hash into the same place, the worst case is still O(n^2). suppose our hash function is h(n) = n mod 10. array: 2,12,32,52,42. On Fri, Jun 3, 2011 at 1:01 AM, Harshal hc4...@gmail.com wrote: you can check if the element to be inserted next is same as the node value while inserting itself. Why to do a separate inorder traversal.. On Fri, Jun 3, 2011 at 12:56 AM, Supraja Jayakumar suprajasank...@gmail.com wrote: Hi Inserting into BST and break on same element will detect duplicates. But in any case, this is still O(2n) ? - once for inserting them in to the tree and another for the inorder read. Correct me if wrong. Rgds Supraja J On Thu, Jun 2, 2011 at 1:11 PM, Harshal hc4...@gmail.com wrote: @Anurag: XOR wont work here, 1 element is repeated, not 1 element is unique. Read the question again. Keep inserting elements in a BST and break once you find the same element. O(nlogn) On Fri, Jun 3, 2011 at 12:38 AM, Anurag Narain anuragnar...@gmail.com wrote: take X-OR of all the elements.the one which has no duplicate will be left and rest all will be reduced to zero. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- Harshal Choudhary, III Year B.Tech CSE, NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- U -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sanjay Ahuja, Analyst, Financing
