@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
O
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.
what is the time complexity for the code ?
#include
using namespace std;
main()
{
int arr[] = { 2,3,4,9,2,7};
int *ptr1 = &arr[0];
int *ptr2 = &arr[1];
const int SIZE = sizeof arr / sizeof arr[0];
while(1)
{
if(*ptr1 == *ptr2)
@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 unsub
http://ideone.com/vuAse
--
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/-/rbiZjy8dcgEJ.
To post to this group, send email to algogeeks@googlegroups.com.
To un
Could u please tell me the way to find number repeated odd number of time
using X-oR..??
On Sunday, 27 November 2011 00:49:59 UTC+5:30, Gene 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
@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 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 so
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 wrote:
> Given : 4 2 8 9 5 1 9
>
> sort the array.
>
> sorting: 1 2 4 5 8 9 9
>
> for ( i = 0 ;
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:
Yup Gene ..rightly said and very well pointed out :) ..My Mistake :(
On Sun, Nov 27, 2011 at 12:49 AM, Gene 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
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 ite
Good thinking. Note that this is the bitmap solution I described.
You're just storing the bitmap in the sign bits of the input.
On Nov 26, 12:12 pm, bharath sriram wrote:
> *Assumptions*:
> - All positive elements in the array
> - All elements in array are in range 0 to (n-1) [ n - # of elements
^^+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 b
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage 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 wrote:
>
>> @kunzmilan :
>> Can u please maintain the clarity ?
@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 wrote:
> @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
@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 wrote:
>
>
> On 24 lis, 09:09, kumar raja wrote:
> > @kunzmilan : i did not get u, once explain with example...
On 24 lis, 09:09, kumar raja wrote:
> @kunzmilan : i did not get u, once explain with example...
>
> On 23 November 2011 23:47, kunzmilan 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.
kunzmila
Finding duplicates in a multiset is a pretty standard problem. I've
only ever heard of two solutions, and it's unlikely there are others.
One is to sort, which will place duplicates adjacent to each other, so
you can find them by comparing a[i] with a[i+i] for all I. This
algorithm is O(sorting
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 wrote:
> @shady : i am not sure , if u can do it with O(n) space as well it is fine
> for me . but once try
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 T
@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 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, 2
"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 wrote:
> @ravu sairam:
>
> Suppose the hashing is banned ,now what is ur solution???
> Hashing is quite theoretical concept with time complexity O(1).
>
> Bu
@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 sh
hashing is not that simple, can you tell your hash function ?
On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam 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 ha
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 subscr
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan wrote:
>
>
> On 24 lis, 07:02, kumar raja 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.
> >
> >
On 24 lis, 07:02, kumar raja 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
> elemen
27 matches
Mail list logo
