5,337
edits
Interview Algorithms: Difference between revisions
no edit summary
(Created page with "Insights from Leetcode problems. ====Finding a cycle in a linked-list==== Use two runners. <math>O(n)</math><br> Runner 1 goes two steps per iteration.<br> Runner 2 goes one...") |
No edit summary |
||
| Line 7: | Line 7: | ||
Runner 2 goes one step per iteration.<br> | Runner 2 goes one step per iteration.<br> | ||
If there is a cycle, runner 2 will lap runner 1 within 2 cycles. | If there is a cycle, runner 2 will lap runner 1 within 2 cycles. | ||
====Finding duplicates in an array==== | |||
If you have an array of ints where each number appears $n$ times and one number appears $m>n$ times where $gcd(n,m)==1$, | |||
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> | |||