Re: [algogeeks] How to remove duplicate element from array in one pass.
hello all, what if character are not ASCII but are Unicode characters. then we will need 8 KB of memory instead of 32 bytes as in for ASCII's would that also be considered as Constant space( O(1) ) as it is independent of input size ?? -- 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 O(1) extra memory is allowed: O(n) time and O(1) space. Input data not stored. https://github.com/swagatata/ds_and_algos/blob/master/cpp/trivia/remove_duplicates_one_pass.cpp See also: No extra memory except input buffer: O(n log n) time O(n) space (can't do better than this). https://github.com/swagatata/ds_and_algos/blob/master/cpp/trivia/remove_duplicates_without_extra_memory.cpp The code is terse but completely correct. Will leave you guys to figure it out by googling. :) Compile and run on linux with g++ -std=c++0x filename.cpp Use a g++ version > 4.5. Note: DevC++ uses an obsolete compiler. Will not work on it. -- DK -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MxRwQO9hgPcJ. 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.
int x;
set s;
set :: 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 wrote:
> 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
> wrote:
> > question is in c++
> >
> > On Fri, Jun 3, 2011 at 7:48 AM, sanjay ahuja >
> > 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 >
> >> 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
> >> >
> >> > wrote:
> >> >>
> >> >> Hi
> >> >>
> >> >> I think multi hash table will solve this problem.
> >> >>
> >> >> Thanks
> >> >> Supraja J
> >> >>
> >> >> On Thu, Jun 2, 2011 at 1:37 PM, Harshal 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 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
> >> 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 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
> >> >> 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, In
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.
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 wrote:
> C implementation:
>
>
> #include
>
> 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.
C implementation:
#include
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.
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.
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 wrote: > question is in c++ > > On Fri, Jun 3, 2011 at 7:48 AM, sanjay ahuja > 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 >> 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 >> > >> > wrote: >> >> >> >> Hi >> >> >> >> I think multi hash table will solve this problem. >> >> >> >> Thanks >> >> Supraja J >> >> >> >> On Thu, Jun 2, 2011 at 1:37 PM, Harshal 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 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 >> 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 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 >> >> 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?h
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 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 > 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 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 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 > 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 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 > >> 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...@goog
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 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 > wrote: >> >> Hi >> >> I think multi hash table will solve this problem. >> >> Thanks >> Supraja J >> >> On Thu, Jun 2, 2011 at 1:37 PM, Harshal 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 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 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 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 >> 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, sen
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 wrote: > Hi > > I think multi hash table will solve this problem. > > Thanks > Supraja J > > > On Thu, Jun 2, 2011 at 1:37 PM, Harshal 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 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 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 > 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.
Hi I think multi hash table will solve this problem. Thanks Supraja J On Thu, Jun 2, 2011 at 1:37 PM, Harshal 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 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 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 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.
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 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 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 >>> 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.
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 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 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 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. -- 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 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 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.
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 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 > 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.
@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 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.
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.
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.
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 wrote:
> 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.
