Re: [algogeeks] Re: adobe problem---array
@all: First of all apologize for posting the wrong solution.
The whole idea behind it was first find the xor of all array elements and
this will have xor of only those value which got repeated once and thrice
b'cos element which got repeated twice gets nullified. Now intention behind
xoring it again was to remove the element which got repeated once. and
checking the previous value would catch the element which got repeated
thrice which allows us to break through the loop. But for some corner cases
it fails. Thanks all of you to bring it to notice. Will work on it to find
something better which covers all cases.
On Fri, Jul 9, 2010 at 6:39 AM, Ashish Goel wrote:
> i like the idea whereby when you xor again with all xored, essentially, we
> are removing one xor and the result would be the left number(which were
> repeated odd number of times)
>
> however, this will simply not work when
>
> a] there are multiple single numbers like
> 1,2,1,3,1,4,5
>
> b] this would need two occurrence of three time repeated numbers to be
> adjacent
>
> eg : for
> {5,3,3,1,5,7,7,5,8,8} this won't work
>
>
>
> but what i think is that a bit modification of this approach can be used to
> identify the numbers which occur odd times
> so the new set would be {5,1,5,5} now can we proceed from here, still
> thinking...
>
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Fri, Jul 9, 2010 at 1:10 AM, Anand wrote:
>
>> One more approach using XOR to find the element repeated thrice.
>> Complexity: O(n).
>> Space :0
>>
>> http://codepad.org/p82TGhjR
>>
>> main()
>>
>>
>> {
>> int arr[]= {5,3,3,1,5,5,7,7,8,8};
>>
>>
>>
>> int len, set_bit_no, x,y,i;
>>
>> int xor, prev;
>> len = sizeof(arr)/sizeof(arr[0]);
>>
>>
>>
>> xor = arr[0];
>> x = y=0;
>>
>>
>> for(i=1;i>
>> {
>> xor ^= arr[i];
>> }
>>
>> printf("xor:%d\n",xor);
>>
>> for(i=0;i>
>> {
>> xor ^= arr[i];
>> if(xor == 0 && prev == arr[i])
>>
>>
>>
>> {
>>printf("Found:%d\n", arr[i]);
>>
>>break;
>> }
>> prev = arr[i];
>>
>> }
>> }
>>
>>
>>
>> On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal
>> wrote:
>>
>>> @ any solution less then nlogn would do + O(1) space
>>>
>>>
>>> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>>>
@jalaj
Are we looking for a better than )(nlogn) time and O(1) space
solution? What if our target?
If a solution is required simple, then as mentioned by Satya, sort the
numbers in O(nlogn) time and scan once in O(n) time. So we get the
number repeated 3 times in O(nlogn) time and O(1) space.
Sourav
On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
> > I am sceptical whether any XOR solution exits for your question.
But if
> > the question is modified as :
>
> > *Only one number repeats once,* some no.s repeat twice and only one
number
> > repeat thrice, here is the XOR solution for that.
>
> > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
> > in the example 1 repeats once and 5 repeats thrice.
>
> > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
times
> > nullify) -O(N)
>
> > ( let x=1, y=5
> > As we know the no. repeating once and the no. repeating thrice are
unequal,
> > there must exist some bit 'k' such that x[k]!=y[k]. There may be
more than
> > such bits in x and y. But one such bit certainly yields T[k]=1
after x^y)
>
> > 2> Now traverse along each bit of T( in binary) from left or right
and
> > consider T[i] =1 which is encountered first. store it . let b=i;
> > (O(M) time and O(M) space to store binary if M is the bit length
of T.)
>
> > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
time
> > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain
O(N))
>
> > 4> T0= XOR( all elements in given array having bit b as 0) (O(N)
time and
> > O(M) space)
>
> > One of (T1,T0) gives the no. that repeats once and the other gives
the no
> > that repeats thrice.
>
> > 6> Now traverse the along array A and compute count for T1 and T0.
The
> > count that equals 3 gives the corresponding no. repeating thrice.
-O(N)
>
> > Time complexity is O(N+M) . Linear
> > space complexity is O(M) to store binary form.
>
> > But this algo certainly fails if more than one no. repeats once.
>
> --
> Thanks & Regards,
> Priyanka Chatterjee
> Final Year Undergraduate Student,
> Computer Science & Engineering,
> National Institute Of Technology,Durgapur
> Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google
>>
Re: [algogeeks] Re: adobe problem---array
i like the idea whereby when you xor again with all xored, essentially, we
are removing one xor and the result would be the left number(which were
repeated odd number of times)
however, this will simply not work when
a] there are multiple single numbers like
1,2,1,3,1,4,5
b] this would need two occurrence of three time repeated numbers to be
adjacent
eg : for
{5,3,3,1,5,7,7,5,8,8} this won't work
but what i think is that a bit modification of this approach can be used to
identify the numbers which occur odd times
so the new set would be {5,1,5,5} now can we proceed from here, still
thinking...
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Fri, Jul 9, 2010 at 1:10 AM, Anand wrote:
> One more approach using XOR to find the element repeated thrice.
> Complexity: O(n).
> Space :0
>
> http://codepad.org/p82TGhjR
>
> main()
>
> {
> int arr[]= {5,3,3,1,5,5,7,7,8,8};
>
>
> int len, set_bit_no, x,y,i;
>
> int xor, prev;
> len = sizeof(arr)/sizeof(arr[0]);
>
>
> xor = arr[0];
> x = y=0;
>
>
> for(i=1;i
> {
> xor ^= arr[i];
> }
>
> printf("xor:%d\n",xor);
>
> for(i=0;i
> {
> xor ^= arr[i];
> if(xor == 0 && prev == arr[i])
>
>
> {
>printf("Found:%d\n", arr[i]);
>
>break;
> }
> prev = arr[i];
>
> }
> }
>
>
>
> On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal
> wrote:
>
>> @ any solution less then nlogn would do + O(1) space
>>
>>
>> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>>
>>> @jalaj
>>>
>>> Are we looking for a better than )(nlogn) time and O(1) space
>>> solution? What if our target?
>>>
>>> If a solution is required simple, then as mentioned by Satya, sort the
>>> numbers in O(nlogn) time and scan once in O(n) time. So we get the
>>> number repeated 3 times in O(nlogn) time and O(1) space.
>>>
>>> Sourav
>>>
>>> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
>>> > > I am sceptical whether any XOR solution exits for your question. But
>>> if
>>> > > the question is modified as :
>>> >
>>> > > *Only one number repeats once,* some no.s repeat twice and only one
>>> number
>>> > > repeat thrice, here is the XOR solution for that.
>>> >
>>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
>>> > > in the example 1 repeats once and 5 repeats thrice.
>>> >
>>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
>>> times
>>> > > nullify) -O(N)
>>> >
>>> > > ( let x=1, y=5
>>> > > As we know the no. repeating once and the no. repeating thrice are
>>> unequal,
>>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
>>> than
>>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
>>> x^y)
>>> >
>>> > > 2> Now traverse along each bit of T( in binary) from left or right
>>> and
>>> > > consider T[i] =1 which is encountered first. store it . let b=i;
>>> > > (O(M) time and O(M) space to store binary if M is the bit length of
>>> T.)
>>> >
>>> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
>>> time
>>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain
>>> O(N))
>>> >
>>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
>>> and
>>> > > O(M) space)
>>> >
>>> > > One of (T1,T0) gives the no. that repeats once and the other gives
>>> the no
>>> > > that repeats thrice.
>>> >
>>> > > 6> Now traverse the along array A and compute count for T1 and T0.
>>> The
>>> > > count that equals 3 gives the corresponding no. repeating thrice.
>>> -O(N)
>>> >
>>> > > Time complexity is O(N+M) . Linear
>>> > > space complexity is O(M) to store binary form.
>>> >
>>> > > But this algo certainly fails if more than one no. repeats once.
>>> >
>>> > --
>>> > Thanks & Regards,
>>> > Priyanka Chatterjee
>>> > Final Year Undergraduate Student,
>>> > Computer Science & Engineering,
>>> > National Institute Of Technology,Durgapur
>>> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>>> >
>>> > - Show quoted text -
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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,
>> Jalaj Jaiswal
>> +919026283397
>> B.TECH IT
>> IIIT ALLAHABAD
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 Gee
Re: [algogeeks] Re: adobe problem---array
>
> @Anand- your code wont work for the test case {1,1,1,2}
>
Although few trivial test cases it could crack but the boundary ones
failed. Can you please explain what exactly you tried to do , your algorithm
is not clear.
--
Thanks & Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science & Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: adobe problem---array
@Anand: Awesome solution ,it works even if more than 1 number repeats
once...
On 9 July 2010 01:10, Anand wrote:
> One more approach using XOR to find the element repeated thrice.
> Complexity: O(n).
> Space :0
>
> http://codepad.org/p82TGhjR
>
> main()
> {
> int arr[]= {5,3,3,1,5,5,7,7,8,8};
>
> int len, set_bit_no, x,y,i;
>
> int xor, prev;
> len = sizeof(arr)/sizeof(arr[0]);
>
> xor = arr[0];
> x = y=0;
>
>
> for(i=1;i
> {
> xor ^= arr[i];
> }
>
> printf("xor:%d\n",xor);
>
> for(i=0;i
> {
> xor ^= arr[i];
> if(xor == 0 && prev == arr[i])
>
> {
>printf("Found:%d\n", arr[i]);
>
>break;
> }
> prev = arr[i];
>
> }
> }
>
>
>
> On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal
> wrote:
>
>> @ any solution less then nlogn would do + O(1) space
>>
>>
>> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>>
>>> @jalaj
>>>
>>> Are we looking for a better than )(nlogn) time and O(1) space
>>> solution? What if our target?
>>>
>>> If a solution is required simple, then as mentioned by Satya, sort the
>>> numbers in O(nlogn) time and scan once in O(n) time. So we get the
>>> number repeated 3 times in O(nlogn) time and O(1) space.
>>>
>>> Sourav
>>>
>>> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
>>> > > I am sceptical whether any XOR solution exits for your question. But
>>> if
>>> > > the question is modified as :
>>> >
>>> > > *Only one number repeats once,* some no.s repeat twice and only one
>>> number
>>> > > repeat thrice, here is the XOR solution for that.
>>> >
>>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
>>> > > in the example 1 repeats once and 5 repeats thrice.
>>> >
>>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
>>> times
>>> > > nullify) -O(N)
>>> >
>>> > > ( let x=1, y=5
>>> > > As we know the no. repeating once and the no. repeating thrice are
>>> unequal,
>>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
>>> than
>>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
>>> x^y)
>>> >
>>> > > 2> Now traverse along each bit of T( in binary) from left or right
>>> and
>>> > > consider T[i] =1 which is encountered first. store it . let b=i;
>>> > > (O(M) time and O(M) space to store binary if M is the bit length of
>>> T.)
>>> >
>>> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
>>> time
>>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain
>>> O(N))
>>> >
>>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
>>> and
>>> > > O(M) space)
>>> >
>>> > > One of (T1,T0) gives the no. that repeats once and the other gives
>>> the no
>>> > > that repeats thrice.
>>> >
>>> > > 6> Now traverse the along array A and compute count for T1 and T0.
>>> The
>>> > > count that equals 3 gives the corresponding no. repeating thrice.
>>> -O(N)
>>> >
>>> > > Time complexity is O(N+M) . Linear
>>> > > space complexity is O(M) to store binary form.
>>> >
>>> > > But this algo certainly fails if more than one no. repeats once.
>>> >
>>> > --
>>> > Thanks & Regards,
>>> > Priyanka Chatterjee
>>> > Final Year Undergraduate Student,
>>> > Computer Science & Engineering,
>>> > National Institute Of Technology,Durgapur
>>> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>>> >
>>> > - Show quoted text -
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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,
>> Jalaj Jaiswal
>> +919026283397
>> B.TECH IT
>> IIIT ALLAHABAD
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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.
>
--
Thanks & Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science & Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from t
Re: [algogeeks] Re: adobe problem---array
Then do a inplace merge sort / a quick sort and then get a number which
repeats 3 times
On Thu, Jul 8, 2010 at 7:16 PM, jalaj jaiswal wrote:
> @ any solution less then nlogn would do + O(1) space
>
>
> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>
>> @jalaj
>>
>> Are we looking for a better than )(nlogn) time and O(1) space
>> solution? What if our target?
>>
>> If a solution is required simple, then as mentioned by Satya, sort the
>> numbers in O(nlogn) time and scan once in O(n) time. So we get the
>> number repeated 3 times in O(nlogn) time and O(1) space.
>>
>> Sourav
>>
>> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
>> > > I am sceptical whether any XOR solution exits for your question. But
>> if
>> > > the question is modified as :
>> >
>> > > *Only one number repeats once,* some no.s repeat twice and only one
>> number
>> > > repeat thrice, here is the XOR solution for that.
>> >
>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
>> > > in the example 1 repeats once and 5 repeats thrice.
>> >
>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
>> times
>> > > nullify) -O(N)
>> >
>> > > ( let x=1, y=5
>> > > As we know the no. repeating once and the no. repeating thrice are
>> unequal,
>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
>> than
>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
>> x^y)
>> >
>> > > 2> Now traverse along each bit of T( in binary) from left or right
>> and
>> > > consider T[i] =1 which is encountered first. store it . let b=i;
>> > > (O(M) time and O(M) space to store binary if M is the bit length of
>> T.)
>> >
>> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
>> time
>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain O(N))
>> >
>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
>> and
>> > > O(M) space)
>> >
>> > > One of (T1,T0) gives the no. that repeats once and the other gives
>> the no
>> > > that repeats thrice.
>> >
>> > > 6> Now traverse the along array A and compute count for T1 and T0. The
>> > > count that equals 3 gives the corresponding no. repeating thrice.
>> -O(N)
>> >
>> > > Time complexity is O(N+M) . Linear
>> > > space complexity is O(M) to store binary form.
>> >
>> > > But this algo certainly fails if more than one no. repeats once.
>> >
>> > --
>> > Thanks & Regards,
>> > Priyanka Chatterjee
>> > Final Year Undergraduate Student,
>> > Computer Science & Engineering,
>> > National Institute Of Technology,Durgapur
>> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: adobe problem---array
@anand
Your code wont work for many of the cases
int arr[]= {5,3,1,11,5,7,11,5,8};
please check the correctness before posting any solution
--
Regards
Jitendra Kushwaha
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: adobe problem---array
it assumes that a number which just appear 1 times is also unique whereas
there can be many numbers which appear just 1 times
On Fri, Jul 9, 2010 at 1:10 AM, Anand wrote:
> One more approach using XOR to find the element repeated thrice.
> Complexity: O(n).
> Space :0
>
> http://codepad.org/p82TGhjR
>
> main()
> {
> int arr[]= {5,3,3,1,5,5,7,7,8,8};
>
> int len, set_bit_no, x,y,i;
>
> int xor, prev;
> len = sizeof(arr)/sizeof(arr[0]);
>
> xor = arr[0];
> x = y=0;
>
>
> for(i=1;i
> {
> xor ^= arr[i];
> }
>
> printf("xor:%d\n",xor);
>
> for(i=0;i
> {
> xor ^= arr[i];
> if(xor == 0 && prev == arr[i])
>
> {
>printf("Found:%d\n", arr[i]);
>
>break;
> }
> prev = arr[i];
>
> }
> }
>
>
>
> On Thu, Jul 8, 2010 at 6:46 AM, jalaj jaiswal
> wrote:
>
>> @ any solution less then nlogn would do + O(1) space
>>
>>
>> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>>
>>> @jalaj
>>>
>>> Are we looking for a better than )(nlogn) time and O(1) space
>>> solution? What if our target?
>>>
>>> If a solution is required simple, then as mentioned by Satya, sort the
>>> numbers in O(nlogn) time and scan once in O(n) time. So we get the
>>> number repeated 3 times in O(nlogn) time and O(1) space.
>>>
>>> Sourav
>>>
>>> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
>>> > > I am sceptical whether any XOR solution exits for your question. But
>>> if
>>> > > the question is modified as :
>>> >
>>> > > *Only one number repeats once,* some no.s repeat twice and only one
>>> number
>>> > > repeat thrice, here is the XOR solution for that.
>>> >
>>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
>>> > > in the example 1 repeats once and 5 repeats thrice.
>>> >
>>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
>>> times
>>> > > nullify) -O(N)
>>> >
>>> > > ( let x=1, y=5
>>> > > As we know the no. repeating once and the no. repeating thrice are
>>> unequal,
>>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
>>> than
>>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
>>> x^y)
>>> >
>>> > > 2> Now traverse along each bit of T( in binary) from left or right
>>> and
>>> > > consider T[i] =1 which is encountered first. store it . let b=i;
>>> > > (O(M) time and O(M) space to store binary if M is the bit length of
>>> T.)
>>> >
>>> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
>>> time
>>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain
>>> O(N))
>>> >
>>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
>>> and
>>> > > O(M) space)
>>> >
>>> > > One of (T1,T0) gives the no. that repeats once and the other gives
>>> the no
>>> > > that repeats thrice.
>>> >
>>> > > 6> Now traverse the along array A and compute count for T1 and T0.
>>> The
>>> > > count that equals 3 gives the corresponding no. repeating thrice.
>>> -O(N)
>>> >
>>> > > Time complexity is O(N+M) . Linear
>>> > > space complexity is O(M) to store binary form.
>>> >
>>> > > But this algo certainly fails if more than one no. repeats once.
>>> >
>>> > --
>>> > Thanks & Regards,
>>> > Priyanka Chatterjee
>>> > Final Year Undergraduate Student,
>>> > Computer Science & Engineering,
>>> > National Institute Of Technology,Durgapur
>>> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>>> >
>>> > - Show quoted text -
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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,
>> Jalaj Jaiswal
>> +919026283397
>> B.TECH IT
>> IIIT ALLAHABAD
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.
Re: [algogeeks] Re: adobe problem---array
One more approach using XOR to find the element repeated thrice.
Complexity: O(n).
Space :0
http://codepad.org/p82TGhjR
main()
{
int arr[]= {5,3,3,1,5,5,7,7,8,8};
int len, set_bit_no, x,y,i;
int xor, prev;
len = sizeof(arr)/sizeof(arr[0]);
xor = arr[0];
x = y=0;
for(i=1;iwrote:
> @ any solution less then nlogn would do + O(1) space
>
>
> On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
>
>> @jalaj
>>
>> Are we looking for a better than )(nlogn) time and O(1) space
>> solution? What if our target?
>>
>> If a solution is required simple, then as mentioned by Satya, sort the
>> numbers in O(nlogn) time and scan once in O(n) time. So we get the
>> number repeated 3 times in O(nlogn) time and O(1) space.
>>
>> Sourav
>>
>> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
>> > > I am sceptical whether any XOR solution exits for your question. But
>> if
>> > > the question is modified as :
>> >
>> > > *Only one number repeats once,* some no.s repeat twice and only one
>> number
>> > > repeat thrice, here is the XOR solution for that.
>> >
>> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
>> > > in the example 1 repeats once and 5 repeats thrice.
>> >
>> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
>> times
>> > > nullify) -O(N)
>> >
>> > > ( let x=1, y=5
>> > > As we know the no. repeating once and the no. repeating thrice are
>> unequal,
>> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
>> than
>> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
>> x^y)
>> >
>> > > 2> Now traverse along each bit of T( in binary) from left or right
>> and
>> > > consider T[i] =1 which is encountered first. store it . let b=i;
>> > > (O(M) time and O(M) space to store binary if M is the bit length of
>> T.)
>> >
>> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
>> time
>> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain O(N))
>> >
>> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
>> and
>> > > O(M) space)
>> >
>> > > One of (T1,T0) gives the no. that repeats once and the other gives
>> the no
>> > > that repeats thrice.
>> >
>> > > 6> Now traverse the along array A and compute count for T1 and T0. The
>> > > count that equals 3 gives the corresponding no. repeating thrice.
>> -O(N)
>> >
>> > > Time complexity is O(N+M) . Linear
>> > > space complexity is O(M) to store binary form.
>> >
>> > > But this algo certainly fails if more than one no. repeats once.
>> >
>> > --
>> > Thanks & Regards,
>> > Priyanka Chatterjee
>> > Final Year Undergraduate Student,
>> > Computer Science & Engineering,
>> > National Institute Of Technology,Durgapur
>> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
>> >
>> > - Show quoted text -
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: adobe problem---array
@ any solution less then nlogn would do + O(1) space
On Thu, Jul 8, 2010 at 12:38 AM, souravsain wrote:
> @jalaj
>
> Are we looking for a better than )(nlogn) time and O(1) space
> solution? What if our target?
>
> If a solution is required simple, then as mentioned by Satya, sort the
> numbers in O(nlogn) time and scan once in O(n) time. So we get the
> number repeated 3 times in O(nlogn) time and O(1) space.
>
> Sourav
>
> On Jul 7, 7:36 pm, Priyanka Chatterjee wrote:
> > > I am sceptical whether any XOR solution exits for your question. But
> if
> > > the question is modified as :
> >
> > > *Only one number repeats once,* some no.s repeat twice and only one
> number
> > > repeat thrice, here is the XOR solution for that.
> >
> > > suppose the sample array is A[]={1, 3,3,5,5,5, 7,7,8,8}
> > > in the example 1 repeats once and 5 repeats thrice.
> >
> > > 1>let T= XOR( all elements)= 1^5. (all elements occurring even no of
> times
> > > nullify) -O(N)
> >
> > > ( let x=1, y=5
> > > As we know the no. repeating once and the no. repeating thrice are
> unequal,
> > > there must exist some bit 'k' such that x[k]!=y[k]. There may be more
> than
> > > such bits in x and y. But one such bit certainly yields T[k]=1 after
> x^y)
> >
> > > 2> Now traverse along each bit of T( in binary) from left or right and
> > > consider T[i] =1 which is encountered first. store it . let b=i;
> > > (O(M) time and O(M) space to store binary if M is the bit length of
> T.)
> >
> > > 3> T1= XOR(all elements in given array having bit b as 1). (O(N)
> time
> > > and O(M) space) ( time is O(MN) but as M<=32 , complexity remain O(N))
> >
> > > 4> T0= XOR( all elements in given array having bit b as 0) (O(N) time
> and
> > > O(M) space)
> >
> > > One of (T1,T0) gives the no. that repeats once and the other gives the
> no
> > > that repeats thrice.
> >
> > > 6> Now traverse the along array A and compute count for T1 and T0. The
> > > count that equals 3 gives the corresponding no. repeating thrice. -O(N)
> >
> > > Time complexity is O(N+M) . Linear
> > > space complexity is O(M) to store binary form.
> >
> > > But this algo certainly fails if more than one no. repeats once.
> >
> > --
> > Thanks & Regards,
> > Priyanka Chatterjee
> > Final Year Undergraduate Student,
> > Computer Science & Engineering,
> > National Institute Of Technology,Durgapur
> > Indiahttp://priyanka-nit.blogspot.com/- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
