5,321
edits
Interview Algorithms: Difference between revisions
→Finding duplicates in an array
| Line 11: | Line 11: | ||
====Finding duplicates in an array==== | ====Finding duplicates in an array==== | ||
If you have an array of ints where each number appears | If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, | ||
then you count the number of times each bit appears and take it mod <math>n</math>.<br> | then you count the number of times each bit appears and take it mod <math>n</math>.<br> | ||
The remaining bits will remain <math>m \mod n</math> times.<br> | The remaining bits will remain <math>m \mod n</math> times.<br> | ||