@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.
