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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wh65xNNjRksJ. 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.
