Re: [algogeeks] Re: Finding the repeated element
This will help u http://www.geeksforgeeks.org/archives/570 -- 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] Re: Finding the repeated element
@Arun: The referenced algorithm solves the wrong problem. The problem given has n-2 unique elements and 1 element repeated twice. The referenced algorithm has n-1 elements that occur in pairs and one that is unique; xoring will solve this problem, but it won't help solve the given one. Dave On Monday, July 23, 2012 12:55:01 PM UTC-5, Arun Kindra wrote: This will help u http://www.geeksforgeeks.org/archives/570 -- 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/-/EFi5PG1OKTkJ. 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] Re: Finding the repeated element
@deepikaanand (checksum 1 100) will it work ? as i know int has only 32 bits !! Thanks Regards Saurabh Yadav -- 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] Re: Finding the repeated element
@Dave : sorry , i considered sorting a prerequisite for the given problem .
should have read it properly before posting.
On Tue, Dec 6, 2011 at 8:56 PM, Dave dave_and_da...@juno.com wrote:
Atul: The original poster asked for an algorithm that is O(n) in time
and O(1) space. So please tell us how you are going to sort the array
with those limitations.
Dave
On Dec 6, 1:35 am, atul anand atul.87fri...@gmail.com wrote:
Given : 4 2 8 9 5 1 9
sort the array.
sorting: 1 2 4 5 8 9 9
for ( i = 0 ; i len ; i++)
{
if( i != len-1 )
{
if (arr[i]==arr[i+1])
{
printf(\nfound repeated element\n);
break;
}
}
}
On Mon, Nov 28, 2011 at 1:24 AM, Ankur Garg ankurga...@gmail.com
wrote:
Yup Gene ..rightly said and very well pointed out :) ..My Mistake :(
On Sun, Nov 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:
Isn't this overkill? If you're already using a set, just check the set
before you insert each new element, and you'll discover the
duplicates:
S = empty
while i = input item existss
if i in S output i has a duplicate;
insert i in S
end
XOR is generally useful only for detecting a single item that's
included in a list an odd number of times rather than an even number
of times.
On Nov 24, 3:56 pm, Ankur Garg ankurga...@gmail.com wrote:
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements
of
the
array . This wud give us the repeating element as all the elements
coming
once will be 0(xored twice) and repeating element wud be xored
twice .
To code it as follows
int FindSingle(int a[],int n){
setints;
s.insert(a,a+n);
setint::iterator it;
it = s.begin();
int XOR= *it;
it++;
while(it!=s.end()){
XOR =XOR^*it;
it++;}
for(int i=0;in;i++)
XOR=XOR^a[i];
return XOR;
}
On Fri, Nov 25, 2011 at 1:03 AM, kumar raja
rajkumar.cs...@gmail.com
wrote:
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com
wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the
matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja
rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please
elaborate
it...
On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz
wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz
wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal are numbers of repeated elements.
kunzmilan
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com
wrote:
In the given array all the elements occur single time
except
one
element
which occurs 2 times find it in O(n) time and O(1)
space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find
All the
repeated
elements in an array in O(n) time and O(1) space
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
Write the list in the form of a matrix M, e.g.
0 1 0 0...
0 0 1 0...
0 0 0 1...
..etc.,
and its quadratic form M(T)M shows, how many times each
element
repeats.
kunzmilan
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You
Re: [algogeeks] Re: Finding the repeated element
Given : 4 2 8 9 5 1 9
sort the array.
sorting: 1 2 4 5 8 9 9
for ( i = 0 ; i len ; i++)
{
if( i != len-1 )
{
if (arr[i]==arr[i+1])
{
printf(\nfound repeated element\n);
break;
}
}
}
On Mon, Nov 28, 2011 at 1:24 AM, Ankur Garg ankurga...@gmail.com wrote:
Yup Gene ..rightly said and very well pointed out :) ..My Mistake :(
On Sun, Nov 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote:
Isn't this overkill? If you're already using a set, just check the set
before you insert each new element, and you'll discover the
duplicates:
S = empty
while i = input item existss
if i in S output i has a duplicate;
insert i in S
end
XOR is generally useful only for detecting a single item that's
included in a list an odd number of times rather than an even number
of times.
On Nov 24, 3:56 pm, Ankur Garg ankurga...@gmail.com wrote:
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements of
the
array . This wud give us the repeating element as all the elements
coming
once will be 0(xored twice) and repeating element wud be xored twice .
To code it as follows
int FindSingle(int a[],int n){
setints;
s.insert(a,a+n);
setint::iterator it;
it = s.begin();
int XOR= *it;
it++;
while(it!=s.end()){
XOR =XOR^*it;
it++;}
for(int i=0;in;i++)
XOR=XOR^a[i];
return XOR;
}
On Fri, Nov 25, 2011 at 1:03 AM, kumar raja rajkumar.cs...@gmail.com
wrote:
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the
matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja
rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate
it...
On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal are numbers of repeated elements.
kunzmilan
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except
one
element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find
All the
repeated
elements in an array in O(n) time and O(1) space
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
Write the list in the form of a matrix M, e.g.
0 1 0 0...
0 0 1 0...
0 0 0 1...
..etc.,
and its quadratic form M(T)M shows, how many times each
element
repeats.
kunzmilan
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Anup Ghatage
--
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] Re: Finding the repeated element
@kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Re: Finding the repeated element
hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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] Re: Finding the repeated element
@ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Re: Finding the repeated element
find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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] Re: Finding the repeated element
@shady : i am not sure , if u can do it with O(n) space as well it is fine for me . but once try whether it is possible in O(1) space. On 24 November 2011 05:42, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Re: Finding the repeated element
i also doubt about the time and space complexity of the problem, i has been asked a number of times with these constraints but never been answered the required, as far as i remember the best solution to this problem that has been discussed so far is using hashing and that too theoretically having TC and SC of O(n). On Thu, Nov 24, 2011 at 7:12 PM, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Finding the repeated element
i don't think there is an O(n) time solution for this... bcoz there are no constraints on the values, and on the number of values in the array. On Thu, Nov 24, 2011 at 7:15 PM, kumar raja rajkumar.cs...@gmail.comwrote: @shady : i am not sure , if u can do it with O(n) space as well it is fine for me . but once try whether it is possible in O(1) space. On 24 November 2011 05:42, shady sinv...@gmail.com wrote: find it in O(n) time and O(1) space, are you sure that it is possible to do it in O(n) time ? On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote: @ravu sairam: Suppose the hashing is banned ,now what is ur solution??? Hashing is quite theoretical concept with time complexity O(1). But it will not be the case every time.so suggest some other better solution I used to thought of using count array ,but again its size is not O(n), its size should be max-min+1 . and it looks odd. so even if someone want to provide linear time solution using extra space in O(n) it is welcome... On 24 November 2011 05:13, shady sinv...@gmail.com wrote: hashing is not that simple, can you tell your hash function ? On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote: I have an O(n) space and time solution by using hashing . Firstly, make a hash table by using a hash function for each of the number in the array. After that, go through the hash table to see whether there are any repetitions for the same entry. -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- 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] Re: Finding the repeated element
@kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmilan kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Re: Finding the repeated element
@kunzmilan Nice idea, how do you decide the row-size or column-size of the matrix? On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote: @kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Anup Ghatage -- 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] Re: Finding the repeated element
@Anup: Atleast u tell me how the M has formed??? On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote: @kunzmilan Nice idea, how do you decide the row-size or column-size of the matrix? On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote: @kunzmilan : Can u please maintain the clarity ?? How did u find the M if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it... On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote: On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote: @kunzmilan : i did not get u, once explain with example... On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote: Matrix M 0 1 0 0 1 0 1 0 0 multiplied with M(T) 0 0 1 1 1 0 0 0 0 gives 1 0 0 0 2 0 0 0 0. On its diagonal are numbers of repeated elements. kunzmilan On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote: In the given array all the elements occur single time except one element which occurs 2 times find it in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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. -- Anup Ghatage -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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] Re: Finding the repeated element
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements of the
array . This wud give us the repeating element as all the elements coming
once will be 0(xored twice) and repeating element wud be xored twice .
To code it as follows
int FindSingle(int a[],int n){
setints;
s.insert(a,a+n);
setint::iterator it;
it = s.begin();
int XOR= *it;
it++;
while(it!=s.end()){
XOR =XOR^*it;
it++;
}
for(int i=0;in;i++)
XOR=XOR^a[i];
return XOR;
}
On Fri, Nov 25, 2011 at 1:03 AM, kumar raja rajkumar.cs...@gmail.comwrote:
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it...
On 24 November 2011 06:15, kunzmize an kunzmi...@atlas.cz wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal are numbers of repeated elements.
kunzmilan
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except one
element
which occurs 2 times find it in O(n) time and O(1) space.
e.g. 2 3 4 9 3 7
output :3
If such a solution exist can we extend the logic to find All the
repeated
elements in an array in O(n) time and O(1) space
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
Write the list in the form of a matrix M, e.g.
0 1 0 0...
0 0 1 0...
0 0 0 1...
..etc.,
and its quadratic form M(T)M shows, how many times each element
repeats.
kunzmilan
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
Anup Ghatage
--
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.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
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.
--
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.
