@Vikram - sorry to burst your bubble once again. try - [3 3 1 1] even indirect xor'ing could not ensure anything useful.
On 2 November 2012 17:04, Vikram Pradhan <[email protected]> wrote: > @Don :yeah sorry i misinterpreted the if condition ..it'll work fine . > > I've modified my previous sol. and in this sol we do not need to modify > the array . Time complexity O(n) and constant space. > http://ideone.com/s2kR24 > > > > > > On Fri, Nov 2, 2012 at 1:14 AM, Don <[email protected]> wrote: > >> It won't enter an infinite loop in that case. In fact, it would >> immediately return. >> Don >> >> On Oct 31, 2:39 pm, Vikram Pradhan <[email protected]> wrote: >> > @Don It will be an infinite loop for some cases ...like try this i=1, >> and >> > a[1] = 5 , a[5] = 5 >> > >> > *Solution:* >> > >> > As the numbers are from 0 to N-1 so we can xor the value with its index >> in >> > a loop . if the result is 0 then there is no repetition else there is >> some >> > repetition. >> > >> > *int result = 0;* >> > *for(int i=0;i<N;i++)* >> > *{* >> > *result ^= i ^ array[i];* >> > *}* >> > * >> > * >> > *if(result==0)* >> > *There is no repetition.* >> > *else* >> > *There is some repetition.* >> > >> > Time complexity O(N) >> > Space Complexity : constant >> > >> > check this :http://ideone.com/RXyynB >> > >> > As the indexes are from 0 to N-1 and numbers are also from 0 to N-1 in >> > random order. So if there is no repetition then there is exactly two >> copies >> > of same number in set of (values and index) and when we xor all the >> indexes >> > to all the numbers the result will be zero because xor of same no. is >> zero. >> > >> > -- >> > Vikram Pradhan | B.Tech| Computer Science & Engineering | NIT Jalandhar >> | >> > 9740186063 | >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> 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. >> >> > > > -- > Vikram Pradhan | B.Tech| Computer Science & Engineering | NIT Jalandhar | > 9740186063 | > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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 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.
