@Pranav: This could fail if N > sqrt(maxint) and a sufficient number of A[i] have the same value so that A[A[i]] > N*N, which overflows.
Dave On Feb 15, 1:08 am, Pranav <meetpranav...@gmail.com> wrote: > Array 'A' contains N elements st A[i] <=k <N > Now, > > Iterate over the array. > Let k=A[i] > If A[i] > N > > then k=A[i] mod N > > go to A[k] and write A[k] = A[k] + N > > So, lets take a sample array of size 5: 1,2,1,0,4 > > i=0: k=A[i]=1; A[i] <5; A[1] = A[1] + 5 => A[1] = 7 => A = 1,7,1,0,4 > i=1: k=A[i]=7; A[i] > 5; k=A[i] mod N => k=2 => A[2] = A[2] + 5 => > A=1,7,6,0,4 > i=2: k=A[i]=6; A[i] > 5; k=A[i] mod N => k=1 => A[1] = A[1] + 5 => > A=1,12,6,0,4 > i=3: k=A[i]=0; A[i] < 5; k=0 => A[0] = A[0] + 5 => A=6,12,6,0,4 > i=4: k=A[i]=4; A[i] < 5; k=4 => A[4] = A[4] + 5 => A=6,12,6,0,9 > > I'm using the fact that: > > (c*n + a) mod n =a > > Now, while searching, for say i=1, > k=A[i] => k=12 > count=int(k/5) > > Let me know if any test case fails. -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
