you can solve this problem using bitvector/bitset. first scan : scan the array set the bit on odd occurrence and unset on even or 0 occurrence.
second scan : shift all the odd occurring elements in beginning of array and even towards end. third scan : till end of odd occurring elements. take another bit vector on first occurence :if bit is set in bv1 then unset it and set it in bv2. on second occurence : if bv1 is not set and bv2 is set then these are the array elements occuring 3rd time. On Wed, Feb 13, 2013 at 9:27 PM, prakhar singh <[email protected]>wrote: > Yes, thats a valid point Don. > Thats what i meant when i wrote "//is that correct?" in the comments on > the array line in code. > > > int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? > > > On Wed, Feb 13, 2013 at 9:09 PM, Don <[email protected]> wrote: > >> The xor approach only works if there are no values which occur only >> once. But the problem statement indicates that some numbers occur >> once, some occur twice, and one occurs three times. So you will end up >> with prod equal to the xor of all of the values which occur once or >> three times. Put that in your input array and you'll find that you >> don't get the desired output. >> >> I don't know of a solution better than sorting and scanning the array. >> >> Don >> >> On Feb 12, 3:14 pm, prakhar singh <[email protected]> wrote: >> > #include<stdio.h> >> > >> > int main() >> > { >> > int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct? >> > int prod=a[0];int i; >> > for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++) >> > { >> > prod ^= a[i]; >> > } >> > printf("%d\n",prod); //outputs 3, algorithm works as Sachin >> described >> > it; >> > >> > } >> > >> > On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale >> > <[email protected]>wrote: >> > >> > >> > >> > >> > >> > >> > >> > > use ex-or operation for all array elements.. >> > > a^a=0 >> > > a^a^a=a >> > >> > > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B < >> [email protected]>wrote: >> > >> > >> can use counting sort >> > >> > >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota < >> [email protected]>wrote: >> > >> > >>> If we can retrieve ith prime efficiently, we can do the following... >> > >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th >> prime >> > >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i; >> > >>> else prod=prod*ith_prime; >> > >>> 3.repeat it till end >> > >> > >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote: >> > >> > >>>> Given an array of integers where some numbers repeat once, some >> numbers >> > >>>> repeat twice and only one number repeats thrice, how do you find >> the number >> > >>>> that gets repeated 3 times? >> > >> > >>>> Does this problem have an O(n) time and O(1) space solution? >> > >>>> No hashmaps please! >> > >> > >>> -- >> > >>> 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/-/TSPSKlD0FDsJ. >> > >> > >>> To post to this group, send email to [email protected]. >> > >>> To unsubscribe from this group, send email to >> > >>> [email protected]. >> > >>> 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 unsubscribe from this group and stop receiving emails from it, >> send an >> > >> email to [email protected]. >> > >> For more options, visithttps://groups.google.com/groups/opt_out. >> > >> > > -- >> > > Regards, >> > > Sachin Chitale >> > > Application Engineer SCJP, SCWCD >> > > Contact# : +91 8086284349, 9892159511 >> > > Oracle Corporation >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To unsubscribe from this group and stop receiving emails from it, >> send an >> > > email to [email protected]. >> > > For more options, visithttps://groups.google.com/groups/opt_out. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Regards, Sourabh Kumar Jain +91-8971547841 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
