Interview Algorithms: Difference between revisions
| 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> | ||
Revision as of 03:54, 5 November 2019
Insights from Leetcode problems.
Finding a cycle in a linked-list
Use two runners. \(\displaystyle O(n)\)
Runner 1 goes two steps per iteration.
Runner 2 goes one step per iteration.
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 \(\displaystyle n\) times and one number appears \(\displaystyle m\gt n\) times where \(\displaystyle gcd(n,m)==1\),
then you count the number of times each bit appears and take it mod \(\displaystyle n\).
The remaining bits will remain \(\displaystyle m \mod n\) times.